首页 > 代码库 > Java技术之HashMap
Java技术之HashMap
哈希映像，它在Java中经常用到，主要保存key-value数据，其中HashMap实现了Map接口。系统通过Hash算法来计算key-value存储的位置，这样可以快速存取Map的key-value对。
HashMap的存储实现
HashMap采用一种所谓的“Hash 算法”来决定每个元素的存储位置。下面结合源码解析HashMap的实现。
HashMap<String, String> map=new HashMap<String, String>();
map.put("A", "Forsta");
map.put("B", "Sam");
map.put("C", "Jack");
HashMap通过put方法将key-value保存到hashmap中。
1 public V put(K key, V value) { 2 if (key == null) 3 return putForNullKey(value); 4 int hash = hash(key.hashCode()); 5 int i = indexFor(hash, table.length); 6 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 7 Object k; 8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9 V oldValue =http://www.mamicode.com/ e.value;10 e.value =http://www.mamicode.com/ value;11 e.recordAccess(this);12 return oldValue;13 }14 }15 16 modCount++;17 addEntry(hash, key, value, i);18 return null;19 }
保存key-value具体的流程是，首先获取到key,判断key是否为null,如果为null，则直接将value保存到key=null处。如果所求key关键字已经存储在Hash表中，则覆盖当前位置。如果没有保存就直接添加一个Entry,插入表中。新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部。
否则首先计算key的hash值 获取key对象的hashCode---Hash算法---求得表索引值。
1 static int hash(int h) {2 h ^= (h >>> 20) ^ (h >>> 12);3 return h ^ (h >>> 7) ^ (h >>> 4);4 }
1 static int indexFor(int h, int length) {2 return h & (length-1);3 }
这个方法非常巧妙，它总是通过 h &(table.length -1) 来得到该对象的保存位置。table.length-1保证返回索引小于表长，一定位于表中。
1 void addEntry(int hash, K key, V value, int bucketIndex) {2 Entry<K,V> e = table[bucketIndex];3 table[bucketIndex] = new Entry<>(hash, key, value, e);4 if (size++ >= threshold)5 resize(2 * table.length);6 }
addEntry方法，将新插入的Entry放到数组表中，如果之前表中已经有Entry数据了，则将新添加的Entry对象next指向原来的对象，形成Entry链；如果没有，则指向空。
如果数据超过threshold值，则进行扩容，但每次都原来的2倍。
HashMap具体的结构如下图
HashMap 的读取实现
当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：
1 public V get(Object key) { 2 if (key == null) 3 return getForNullKey(); 4 int hash = hash(key.hashCode()); 5 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 6 e != null; 7 e = e.next) { 8 Object k; 9 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))10 return e.value;11 }12 return null;13 }