java8 hashmap实现原理探究-亚博电竞手机版

前言：java8之后新增挺多新东西，在网上找了些相关资料，关于hashmap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看。图和有些内容参考的这个文章：http://www.importnew.com/16599.html

hashmap的存储结构如图：一个桶（bucket）上的节点多于8个则存储结构是红黑树，小于8个是单向链表。

1：hashmap的一些属性

public class hashmap extends abstractmap implements map, cloneable, serializable {      private static final long serialversionuid = 362498820763181265l;      // 默认的初始容量是16     static final int default_initial_capacity = 1 << 4;      // 最大容量     static final int maximum_capacity = 1 << 30;      // 默认的填充因子(以前的版本也有叫加载因子的)     static final float default_load_factor = 0.75f;      // 这是一个阈值，当桶(bucket)上的链表数大于这个值时会转成红黑树，put方法的代码里有用到     static final int treeify_threshold = 8;      // 也是阈值同上一个相反，当桶(bucket)上的链表数小于这个值时树转链表     static final int untreeify_threshold = 6;      // 看源码注释里说是：树的最小的容量，至少是 4 x treeify_threshold = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64     static final int min_treeify_capacity = 64;      // 存储元素的数组，总是2的倍数     transient node[] table;      transient set> entryset;      // 存放元素的个数，注意这个不等于数组的长度。     transient int size;      // 每次扩容和更改map结构的计数器     transient int modcount;      // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容     int threshold;      // 填充因子     final float loadfactor;

2：hashmap的构造方法

// 指定初始容量和填充因子的构造方法 public hashmap(int initialcapacity, float loadfactor) {     // 指定的初始容量非负     if (initialcapacity < 0)         throw new illegalargumentexception(illegal initial capacity:                                               initialcapacity);     // 如果指定的初始容量大于最大容量,置为最大容量     if (initialcapacity > maximum_capacity)         initialcapacity = maximum_capacity;     // 填充比为正     if (loadfactor <= 0 || float.isnan(loadfactor))         throw new illegalargumentexception(illegal load factor:                                               loadfactor);     this.loadfactor = loadfactor;     // 指定容量后，tablesizefor方法计算出临界值，put数据的时候如果超出该值就会扩容，该值肯定也是2的倍数     // 指定的初始容量没有保存下来，只用来生成了一个临界值     this.threshold = tablesizefor(initialcapacity); }  // 该方法保证总是返回大于cap并且是2的倍数的值，比如传入999 返回1024 static final int tablesizefor(int cap) {     int n = cap - 1;     // 向右做无符号位移     n |= n >>> 1;     n |= n >>> 2;     n |= n >>> 4;     n |= n >>> 8;     n |= n >>> 16;     // 三目运算符的嵌套     return (n < 0) ? 1 : (n >= maximum_capacity) ? maximum_capacity : n   1; }  //构造函数2 public hashmap(int initialcapacity) {     this(initialcapacity, default_load_factor); }  //构造函数3 public hashmap() {     this.loadfactor = default_load_factor; // all other fields defaulted }

3：get和put的时候确定元素在数组中的位置

static final int hash(object key) {     int h;     return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16); }

要确定位置

第一步：首先是要计算key的hash码，是一个int类型数字。那后面的 h >>> 16 源码注释的说法是：为了避免hash碰撞(hash collisons)将高位分散到低位上了，这是综合考虑了速度，性能等各方面因素之后做出的。

第二步： h是hash码，length是上面node[]数组的长度，做与运算 h & （length-1）。由于length是2的倍数-1后它的二进制码都是1而1与上其他数的结果可能是0也可能是1，这样保证运算后的均匀性。也就是hash方法保证了结果的均匀性，这点非常重要，会极大的影响hashmap的put和get性能。看下图对比：

图3.1是非对称的hash结果

图3.2是均衡的hash结果

这两个图的数据不是很多，如果链表长度超过8个会转成红黑树。那个时候看着会更明显，jdk8之前一直是链表，链表查询的复杂度是o(n)而红黑树由于其自身的特点，查询的复杂度是o(log(n))。如果hash的结果不均匀会极大影响操作的复杂度。相关的知识这里有一个网上还有个例子来验证：自定义了一个对象来做key，调整hashcode()方法来看put值得时间

public class mutablekeytest {     public static void main(string args[]){         class mykey {             integer i;              public void seti(integer i) {                 this.i = i;             }              public mykey(integer i) {                 this.i = i;             }              @override             public int hashcode() {                 // 如果返回1                 // return 1                 return i;             }              // object作为key存map里，必须实现equals方法             @override             public boolean equals(object obj) {                 if (obj instanceof mykey) {                     return i.equals(((mykey)obj).i);                 } else {                     return false;                 }             }         }          // 我机器配置不高，25000的话正常情况27毫秒，可以用2500万试试，如果hashcode()方法返回1的话，250万就卡死         map map = new hashmap<>(25000,1);         date begin = new date();         for (int i = 0; i < 20000; i  ){             map.put(new mykey(i), "test "   i);         }          date end = new date();         system.out.println("时间(ms) "   (end.gettime() - begin.gettime()));

4：get方法

public v get(object key) {     node e;     return (e = getnode(hash(key), key)) == null ? null : e.value; }  final node getnode(int hash, object key) {     node[] tab; node first, e; int n; k k;     // hash & (length-1)得到红黑树的树根位置或者是链表的表头     if ((tab = table) != null && (n = tab.length) > 0 &&         (first = tab[(n - 1) & hash]) != null) {         if (first.hash == hash && // always check first node             ((k = first.key) == key || (key != null && key.equals(k))))             return first;         if ((e = first.next) != null) {             // 如果是树，遍历红黑树复杂度是o(log(n))，得到节点值             if (first instanceof treenode)                 return ((treenode)first).gettreenode(hash, key);             // else是链表结构             do {                 if (e.hash == hash &&                     ((k = e.key) == key || (key != null && key.equals(k))))                     return e;             } while ((e = e.next) != null);         }     }     return null; }

5 ：put方法，put的时候根据 h & (length – 1) 定位到那个桶然后看是红黑树还是链表再putval

public v put(k key, v value) {        return putval(hash(key), key, value, false, true);    }     final v putval(int hash, k key, v value, boolean onlyifabsent,                   boolean evict) {        node[] tab; node p; int n, i;        // 如果tab为空或长度为0，则分配内存resize()        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        // (n - 1) & hash找到put位置，如果为空,则直接put        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newnode(hash, key, value, null);        else {            node e; k k;            // 第一节节点hash值同，且key值与插入key相同            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof treenode)                // 红黑树的put方法比较复杂，putval之后还要遍历整个树，必要的时候修改值来保证红黑树的特点                e = ((treenode)p).puttreeval(this, tab, hash, key, value);            else {                // 链表                for (int bincount = 0; ;   bincount) {                    if ((e = p.next) == null) {                        // e为空，表示已到表尾也没有找到key值相同节点，则新建节点                        p.next = newnode(hash, key, value, null);                        // 新增节点后如果节点个数到达阈值，则将链表转换为红黑树                        if (bincount >= treeify_threshold - 1) // -1 for 1st                            treeifybin(tab, hash);                        break;                    }                    // 容许空key空value                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            // 更新hash值和key值均相同的节点value值            if (e != null) { // existing mapping for key                v oldvalue = e.value;                if (!onlyifabsent || oldvalue == null)                    e.value = value;                afternodeaccess(e);                return oldvalue;            }        }          modcount;        if (  size > threshold)            resize();        afternodeinsertion(evict);        return null;    }

6：resize方法

final node[] resize() {         node[] oldtab = table;         int oldcap = (oldtab == null) ? 0 : oldtab.length;         int oldthr = threshold;         int newcap, newthr = 0;         if (oldcap > 0) {             if (oldcap >= maximum_capacity) {                 threshold = integer.max_value;                 return oldtab;             }             // 这一句比较重要，可以看出每次扩容是2倍             else if ((newcap = oldcap << 1) < maximum_capacity &&                      oldcap >= default_initial_capacity)                 newthr = oldthr << 1; // double threshold         }         else if (oldthr > 0) // initial capacity was placed in threshold             newcap = oldthr;         else {               // zero initial threshold signifies using defaults             newcap = default_initial_capacity;             newthr = (int)(default_load_factor * default_initial_capacity);         }         if (newthr == 0) {             float ft = (float)newcap * loadfactor;             newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ?                       (int)ft : integer.max_value);         }         threshold = newthr;         @suppresswarnings({"rawtypes","unchecked"})             node[] newtab = (node[])new node[newcap];         table = newtab;         if (oldtab != null) {             for (int j = 0; j < oldcap;   j) {                 node e;                 if ((e = oldtab[j]) != null) {                     oldtab[j] = null;                     if (e.next == null)                         newtab[e.hash & (newcap - 1)] = e;                     else if (e instanceof treenode)                         ((treenode)e).split(this, newtab, j, oldcap);                     else { // preserve order                         node lohead = null, lotail = null;                         node hihead = null, hitail = null;                         node next;                         do {                             next = e.next;                             if ((e.hash & oldcap) == 0) {                                 if (lotail == null)                                     lohead = e;                                 else                                     lotail.next = e;                                 lotail = e;                             }                             else {                                 if (hitail == null)                                     hihead = e;                                 else                                     hitail.next = e;                                 hitail = e;                             }                         } while ((e = next) != null);                         if (lotail != null) {                             lotail.next = null;                             newtab[j] = lohead;                         }                         if (hitail != null) {                             hitail.next = null;                             newtab[j   oldcap] = hihead;                         }                     }                 }             }         }         return newtab;     }