HashMap 源码札记

HashMap 源码笔记

Entry 条目

在引入Entry之前的标准的Map的遍历方法如下：

Set keys = map.keySet( );

if(keys != null) {

Iterator iterator = keys.iterator( );

while(iterator.hasNext( )) {

Object key = iterator.next( );

Object value = map.get(key);

}

每次都要根据key 到Map中找对应的值，低效。

引入以后

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

System.out.println(“Key = ” + entry.getKey() + “, Value = ” + entry.getValue());

}

或者

Map<Integer, Integer> map = new HashMap<Integer, Integer>();

Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();

while (entries.hasNext()) {

Map.Entry<Integer, Integer> entry = entries.next();

System.out.println(“Key = ” + entry.getKey() + “, Value = ” + entry.getValue());

}

每次都是将key-value 一起取出来，效率明显提高了。

/**

* The default initial capacity- MUST be a power of two.

staticfinalintDEFAULT_INITIAL_CAPACITY = 16;

/**

* The load factor used when none specified in constructor.

staticfinalfloatDEFAULT_LOAD_FACTOR = 0.75f;

/**

* The table, resized as necessary. Length MUST Always be a power of two.

* table就是 hash函数拉链法中的数组。显然Entry就是它要装的元素（键值对）。

transient Entry[]table;

/**

* The number of key-value mappings contained in this map.

* 这个table中实际装了多少元素

transientintsize;

/**

* The next size value at which to resize (capacity * load factor).

intthreshold;

/**

*不等装满就扩充容量了，这样能使冲突尽量减少，基本能保证在O（1）能查找到所需元

*/素

if (size++ >=threshold)

resize(2 *table.length);

void resize(intnewCapacity) {

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;

threshold = (int)(newCapacity * loadFactor);

}

public Object put(Object key, Object value) {

  //我们的内部数组是一个 Entry 对象数组

  //Entry[] table;

  //获取哈希码，并映射到一个索引

  int hash = key.hashCode();

  int index = (hash & 0x7FFFFFFF) % table.length;

  //冲突处理，不同的键对象可能拥有相同的哈希，也可能是相同的键对象的修改

   for (Entry e = table[index] ; e != null ; e = e.next) {

    //必须检查键是否相等，原因是不同的键对象可能拥有相同的哈希

    if ((e.hash == hash) && e.key.equals(key)) {

      假如放入的key是已经存在的，就替换原来的&#20540;

      Object old = e.value;

      e.value = value;

      return old;

  //创建一个指向上一个列表开头的新 Entry，

  //用头插法建立的， 即先插入的在上面

  Entry e = new Entry(hash, key, value, table[index]);

  table[index] = e;

  return null;

还有一点要注意的是，HashMap对key进行hash时，不是取的key的key.hashCode()方法，而是对key的hashcode作一些运算得到最后的hash值

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);
}

这是因为在后面的table检索中，使用的函数为

staticint indexFor(inth, int length)

{return h & (length-1);}

如果直接使用 key.hashcode 其除去低length-1位后的部分不会对key在table中的位置产生任何影响，这样只要保持低length-1位不变，

不管高位如何都会冲突，所以就想办法使得高位对其结果也产生影响

HashMap 源码札记

热点推荐