mapから一(Hashmapをよく勉強)
10136 ワード
mapといえば、このjavaにおけるcollectionファミリーの模範、特にhashmapはよく知られているツール類ですが、詳しく見てみましょう.
これはHashmapのインスタンス変数(jdk 1.6)です.hashmapの本質はtransient Entry[]table配列であり、DEFAULT_のように見えます.INITIAL_CAPACITY(デフォルト容量)、MAXIMUM_CAPACITY最大容量(2^30)、DEFAULT_LOAD_FACTORデフォルトマウントファクタ(0.75)は、これらはすべてstaic finalで、デフォルトの構成と境界を検査するために使用されます.また、設定可能な3つも一般的に伝達されるパラメータです.size(これはmapメモリの数対のデータを記録しています)、threshold、loadFactor、それぞれ境界値、ロードファクタ、関係はthreshold=a*loadFactorです.つまり、tableはaサイズに初期化され、thresholdサイズにコンテンツを追加し続けると、tableは自動的に2倍になります.
これは我々がよく使う構造関数であり,基本的には初期容量サイズ,loadFactorの検査,および最も重要なtable=new Entry[capacity];このうちcapacityは私たちがどれだけ制定したのかではなく、彼がどれだけなのか、実際にはinitialCapacityを入力した2よりもちょうど小さい倍数をサイズとして選択しました.
これが有名なput関数です.ここではhashmapが同期していないことが明らかになり、空の値をキーとして受け入れることができます.また、良いkeyのhashcode()が必要であることも明らかになります.ゴミのhashcode()関数を設定すると、
HashMapのhash関数はどうしようもなく,処理された32ビットhashコードが得られた後もtable[]を得たindexの処理を継続する.
簡単な関数で、tableの長さを利用して適切なサイズを切り取り、indexを利用してtableの中でkeyを探し始めました.明らかにこれは空になるまで、または「同じ」keyを見つけてから、addEntryを呼び出さなければ上書きします.
for (Entry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null;
ここで明らかに,新しいEntryを追加するたびにsize++が認められ,size>threshold(前の2つを乗算した結果)ではtable長が2倍になる.
getは基本的に似ていますが、詳しくは言いません.hashmapで実用的なkeySet()を見てみましょう.
明らかにkeyset()は、AbstractSetを実装する内部クラスを返しますが、この内部クラスの実際のset操作は、Haspmapのデータに直接影響します.
この内部クラスではcollectionの隅々まで伴う非常に多くの方法public Iteratoriterator()も見られます
これは同様にHashmapの内部クラスであり、Iteratorを実現する抽象クラスでもあり、hashmapにはkeyset、value、entryがiteratorを返すための3つの内部クラスがHashIteratorを継承しており、iteratorに対するいかなる変更もHashmapの変化をもたらすことが明らかであり、特にexpectedModCount=modCountであることに注意しなければならない.
if (modCount != expectedModCount) throw new ConcurrentModificationException();
ここでは実際にiteratorがHashmapを巡る過程でHashmapの変化(増加と削除はいずれもmodCountの増加をもたらし、前のput関数を見ることができる)が保証されており、iteratorが異常を投げ出すことになるが、put関数をよく見ると、新しく追加するのではなくvalueの交代であればmodCountは変化しないことがわかる.
HashIteratorはうまくいったので、自分のiteratorごとに実現するのは簡単です.
さてHashmapはこれくらいですが、明日はHashmapからもっとmapを広げます
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient volatile int modCount;
これはHashmapのインスタンス変数(jdk 1.6)です.hashmapの本質はtransient Entry[]table配列であり、DEFAULT_のように見えます.INITIAL_CAPACITY(デフォルト容量)、MAXIMUM_CAPACITY最大容量(2^30)、DEFAULT_LOAD_FACTORデフォルトマウントファクタ(0.75)は、これらはすべてstaic finalで、デフォルトの構成と境界を検査するために使用されます.また、設定可能な3つも一般的に伝達されるパラメータです.size(これはmapメモリの数対のデータを記録しています)、threshold、loadFactor、それぞれ境界値、ロードファクタ、関係はthreshold=a*loadFactorです.つまり、tableはaサイズに初期化され、thresholdサイズにコンテンツを追加し続けると、tableは自動的に2倍になります.
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
これは我々がよく使う構造関数であり,基本的には初期容量サイズ,loadFactorの検査,および最も重要なtable=new Entry[capacity];このうちcapacityは私たちがどれだけ制定したのかではなく、彼がどれだけなのか、実際にはinitialCapacityを入力した2よりもちょうど小さい倍数をサイズとして選択しました.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
これが有名なput関数です.ここではhashmapが同期していないことが明らかになり、空の値をキーとして受け入れることができます.また、良いkeyのhashcode()が必要であることも明らかになります.ゴミのhashcode()関数を設定すると、
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
HashMapのhash関数はどうしようもなく,処理された32ビットhashコードが得られた後もtable[]を得たindexの処理を継続する.
static int indexFor(int h, int length) {
return h & (length-1);
}
簡単な関数で、tableの長さを利用して適切なサイズを切り取り、indexを利用してtableの中でkeyを探し始めました.明らかにこれは空になるまで、または「同じ」keyを見つけてから、addEntryを呼び出さなければ上書きします.
for (Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
ここで明らかに,新しいEntryを追加するたびにsize++が認められ,size>threshold(前の2つを乗算した結果)ではtable長が2倍になる.
getは基本的に似ていますが、詳しくは言いません.hashmapで実用的なkeySet()を見てみましょう.
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
明らかにkeyset()は、AbstractSetを実装する内部クラスを返しますが、この内部クラスの実際のset操作は、Haspmapのデータに直接影響します.
この内部クラスではcollectionの隅々まで伴う非常に多くの方法public Iterator
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
これは同様にHashmapの内部クラスであり、Iteratorを実現する抽象クラスでもあり、hashmapにはkeyset、value、entryがiteratorを返すための3つの内部クラスがHashIteratorを継承しており、iteratorに対するいかなる変更もHashmapの変化をもたらすことが明らかであり、特にexpectedModCount=modCountであることに注意しなければならない.
if (modCount != expectedModCount) throw new ConcurrentModificationException();
ここでは実際にiteratorがHashmapを巡る過程でHashmapの変化(増加と削除はいずれもmodCountの増加をもたらし、前のput関数を見ることができる)が保証されており、iteratorが異常を投げ出すことになるが、put関数をよく見ると、新しく追加するのではなくvalueの交代であればmodCountは変化しないことがわかる.
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
HashIteratorはうまくいったので、自分のiteratorごとに実現するのは簡単です.
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
さてHashmapはこれくらいですが、明日はHashmapからもっとmapを広げます