data:2016-10-3 8:54

HashMap 执行原理

内部采用数组与链表的结合形式。 当put时，首先根据key的hash值（调用hashcode方法），来确定该key的value应该位于数组哪个位置。当hash值相同时，调用equal方法判断是否为同一个数据，相同则省略（hashmap不能存一样的值，应该是覆盖关系），不同时，则加入该数组中链表的开头（例如刚开始3号数组中的链表里面有数据 a->b->c, 之后put的一个数据d的key的hash值一样，但是equal 不一样，这时d添加到链表的开头，此时链表的内容即为 d->a->b->c）

hashmap原理.jpg

为了使数据的查询效率提高，所以每个链表最好只有一个值，这样就不需要再去遍历链表了。hash算法采用2^n容量，可以最大避免碰撞几率。
static int indexFor(int h, int length) { return h & (length-1); }

Paste_Image.png

扩容机制： loadfactor 扩容因子。当数据容量超过 当前最大容量*loadfactor时，容量自动扩大2倍，并将当前的数据重新放入新的hashmap中。所以初始的定义大小为2^n的大小最佳。