Java里各种基础容器的实现都是数组外加引用的形式。So,hashmap也不例外。
首先，说句题外话：Hashtable是HashMap这两个难兄难弟，hashtable是hashmap的线程安全版本，它的实现和HashMap实现基本一致，除了它不能包含null值的key和value，并且它在计算hash值和数组索引值的方式要稍微简单一些。对于线程安全的实现，Hashtable简单的将所有操作都标记成synchronized，即对当前实例的锁，这样容易引起一些性能问题，所以目前一般使用性能更好的ConcurrentHashMap。另外，对于HashMap是可以解决同步问题的，通过调用Map Collections.synchronizedMap(Map m)，当然与可以自己在使用地方加锁。
下面进入正题：
我们先来看hashmap构造函数的代码。如下：
this.loadFactor = DEFAULT_LOAD_FACTOR; //装填因子，扩容的时候使用 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); //默认的容量阈值 table = new Entry[DEFAULT_INITIAL_CAPACITY];//构造一个以Entry为对象的数组 init(); //空方法
由以上代码可以看出，初始化hashmap的过程只是初始化了一个Entry类型数组，那Entry类型是什么呢？
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; ....... public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); }/** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that‘s already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } }
可以看出Entry是一个链表一样结构，其中有next域用于指向下一个Entry。
那么我们往hashmap里put一个操作之后都发生了什么呢？还是来看代码。
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); // 对key的哈希在做一个一些移位异或的操作，目的是防止一些鸡肋的key的哈希函数 int i = indexFor(hash, table.length);//返回hash对应的数组的下标。最简单的实现肯定是用hash%length，但这里不是这样，这里的处理很巧妙，下面还会再介绍。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果key存在的话，就替换掉 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //修改次数，用于fail-fast策略 addEntry(hash, key, value, i); //添加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);//如果大小超过阈值的话，resize阈值。resize的过程原存在的Entry会重新计算索引值，并且Entry链的顺序也会发生颠倒（如果还在同一个链中的话）；而该新添加的Entry的索引值也会重新计算。，消耗还是蛮大的，所以如果知道hashmap大小的话，最好还是给个初始值 } return null; }
上文说的利用key的二次hash值求对应的下标的时候，最常规的想法就是用hash%length，但是在jdk里，没这么实现。而是
static int indexFor(int h, int length) { return h & (length-1); }
这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的
n
次方（可以看初始化的代码，扩容的时候也是扩容到2的那次方）。这看上去很简单，其实比较有玄机的，而当数组长度为16时，即为2的n次方时，2的n次方得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int
h)方法对key的hashCode的进一步优化，加入了复杂的异或和位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。这样效率提高了，而且冲突的可能性也减少了。
知道put操作作了什么，get的话就不难了。
就先写到这。
原文：http://www.cnblogs.com/babybluevino/p/3670375.html