jdk6标准类库源码解读 之 数据结构 （三） HashMap<K,V>
HashMap<K,V>[*]此哈希表采用数组+单向链表的方式进行存储。数组中的每个元素，对应哈希算法下的一个哈希值。哈希值重复时，采用链表处理。
/** * 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; static class Entry<K, V> implements Map.Entry<K, V> { final K key; V value; Entry<K, V> next; final int hash; }
[*] 哈希算法基于key的hashCode的返回值进行运算。通过hash和indexFor两个函数运算，得到table数组中的索引序号。
//获取table数组的索引序号i int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length - 1); }
[*] 哈希表存储新元素，put方法，先根据hashCode计算索引序号。首先判断当前hash值有没有存在的对象，有则进行重复处理，将当前值放在链表中；没有则在当前的table当前hash值对应的索引位置，如果需要，可能进行table的容量扩充，扩充算法为直接*2。扩容后，hashMap中的各元素会重新存储分布。（hash值算法不变，但是hash值对应的数组索引会发生变化）。
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //当前存在此hash值对象 for (Entry<K, V> e = table; 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++; //不存在此hash值对象 addEntry(hash, key, value, i); return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K, V> e = table; table = new Entry<K, V>(hash, key, value, e); if (size++ >= threshold) //进行扩容处理，过程中，整个hashMap会重新分布。 resize(2 * table.length); } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry; transfer(newTable); table = newTable; threshold = (int) (newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K, V> e = src; if (e != null) { src = null; do { Entry<K, V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable; newTable = e; e = next; } while (e != null); } } }
[*] 哈希表获取存储的元素，get方法。先根据hashCode计算索引序号。然后顺序逐一比较key值，等号比较和equal比较，查询到需要的对象值。
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K, V> e = table; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
[*]HashTable扩展自Dictionary<K, V>，而非相关的Map接口。同时HashTable是线程同步的。
[*]LinkedHashMap是基于HashMap的有序哈希表。其中存在一个双向循环链表，元素按照加入到哈希表中的顺序排列。
void init() { header = new Entry<K, V>(-1, null, null, null); header.before = header.after = header; } void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K, V> old = table; Entry<K, V> e = new Entry<K, V>(hash, key, value, old); table = e; //循环链表尾部加入一个新的元素 e.addBefore(header); size++; }
[*] ConcurrentHashMap使用了多个segments，每个Segment中使用了类似HashMap的存储结构，进行了存储，不同的是，对于put操作，使用了ReentrantLock进行锁定操作。get操作，没有锁操作。此哈希表，在保证线程安全的前提下，如果存储值在当前hash算法下不过于集中到某个segment中，此容器具有不错的性能。
//ConcurrentHashMap的put方法 public V put(K key, V value) { if (value == null) throw new NullPointerException(); int hash = hash(key.hashCode()); return segmentFor(hash).put(key, hash, value, false); } //Segment的put方法 V put(K key, int hash, V value, boolean onlyIfAbsent) { lock(); try { int c = count; if (c++ > threshold) // ensure capacity rehash(); HashEntry<K, V>[] tab = table; int index = hash & (tab.length - 1); HashEntry<K, V> first = tab; HashEntry<K, V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) e = e.next; V oldValue; if (e != null) { oldValue = e.value; if (!onlyIfAbsent) e.value = value; } else { oldValue = null; ++modCount; tab = new HashEntry<K, V>(key, hash, first, value); count = c; // write-volatile } return oldValue; } finally { unlock(); } }
页:
[1]