电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 从代码层读懂Java HashMap的实现原理（6） [打印本页]

作者: yuyang911220 时间: 2017-4-22 17:25 标题: 从代码层读懂Java HashMap的实现原理（6）

主要代码分析：
public V get(Object key）：如果key不为null，则先求的key的hash值，根据hash值找到在table中的索引，在该索引对应的单链表中查找是否有键值对的key与目标key相等，有就返回对应的value，没有则返回null。如果key为null，则直接从哈希表的第一个位置table[0]对应的链表上查找。记住，key为null的键值对永远都放在以table[0]为头结点的链表中，当然不一定是存放在头结点table[0]中。
public V put(K key, V value)如果key不为null，则同样先求出key的hash值，根据hash值得出在table中的索引，而后遍历对应的单链表，如果单链表中存在与目标key相等的键值对，则将新的value覆盖旧的value，并将旧的value返回，如果找不到与目标key相等的键值对，或者该单链表为空，则将该键值对插入到改单链表的头结点位置（每次新插入的节点都是放在头结点的位置），该操作是有addEntry方法实现的，它的源码如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
      Entry<K,V> e = table[bucketIndex]; //如果要加入的位置有值，将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
      table[bucketIndex] = new Entry<>(hash, key, value, e);
      if (size++ >= threshold) //如果大于临界值就扩容
         resize(2 * table.length); //以2的倍数扩容
}
参数bucketIndex就是indexFor函数计算出来的索引值，第2行代码是取得数组中索引为bucketIndex的Entry对象，第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置，并且将该位置原先的对象设置为新对象的next构成链表。第4行和第5行就是判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容，HashMap扩容是扩为原来的两倍。
如果key为null，则将其添加到table[0]对应的链表中，由putForNullKey（）实现。
// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置
private V putForNullKey(V value) {
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
         if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
         }
      }
      // 如果没有存在key为null的键值对，则直接题阿见到table[0]处!
      modCount++;
      addEntry(0, null, value, 0);
      return null;
}
涉及到的resize扩容方法：
void resize(int newCapacity) {
      Entry[] oldTable = table;
      int oldCapacity = oldTable.length;
      if (oldCapacity == MAXIMUM_CAPACITY) {
         threshold = Integer.MAX_VALUE;
         return;
      }
      Entry[] newTable = new Entry[newCapacity];
      transfer(newTable);//用来将原先table的元素全部移到newTable里面
      table = newTable;  //再将newTable赋值给table
      threshold = (int)(newCapacity * loadFactor);//重新计算临界值
}
它新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。扩容是需要进行数组复制的，非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
hash（）
static int hash(int h) {
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
}
hash值找到对应索引
static int indexFor(int h, int length) {
      return h & (length-1);
}
HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。
length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率。
说明：length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)