本文共 2383 字，大约阅读时间需要 7 分钟。

HashMap的原理

因为计算方式使用的是位与运算，为了防止链表的位置可能多次出现在数组的第一个位置，尽量将HashMap的长度保持为2的次方数——当然在HashMap中也有相应的处理(tableSizeFor方法)来使得数组长度变成2的次方数。

红黑树的基本概念(JDK1.8之后加入)

1. 每个节点是黑色或者是红色；
2. 根节点是黑色；
3. 每个叶子节点(NIL)是黑色 (这里叶子节点，是指为空的叶子节点)；
4. 如果一个节点是红色，则它的子节点必须是黑色；
5. 从一个节点到节点的子孙节点的所有路径上包含相同数目的黑节点。

出现的问题：性价比----时间和空间复杂度

HashMap扩容机制

HashMap中插入东西的时候的思路：

1. 数组 ---- 没元素，直接放；
2. key是不是同一个，如果是，替换value；
3. key不是同一个，且数组有元素，判断是链表或是树 --> 是链表(是否达到树的要求) 没达到就挂链表，达到了就变成树；链表长度达到==8这个数字的时候，会转成红黑树；
4. key不是同一个，且数组有元素，判断是链表或是树 --> 是红黑树，挂到红黑树后面的节点去；
5. 当数组被使用的长度达到数组原始长度的四分之三之后，会开始进行扩容机制，数组长度会翻倍。
6. 这时候，会建立一个新的长度为原长度两倍的数组，然后遍历原数组：
   1. 如果只有一个元素，就直接取模搬过来
   2. 如果数组下是一个链表，就遍历链表之后取模复制过来
   3. 如果是一个树，每个节点再计算一次hash，然后把树打散，一个元素一个元素去拿；

@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)//如果数组是空的，就去拿到next                        newTab[e.hash & (newCap - 1)] = e;//newTab进行位与运算(取余，找位置)，把元素再放进去                    else if (e instanceof TreeNode)//如果是棵树                        ((TreeNode
      
       )e).split(this, newTab, j, oldCap);//split，打散                    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; }
         
        
       
      
     
    
   

hashMap总结

1. hashMap是数组+链表构成的，JDK1.8之后，加入了红黑树；
2. hashMap默认数组初始大小为16，如果随意设置数字，它会自动调整为2的倍数；
3. hashMap链表在长度超过8之后，会自动转换为红黑树，数组扩容之后，会打散红黑树，重新设置；
4. hashMap扩容变化因子是0.75，也就是数组被占用3/4之后，开始扩容；
5. 在第一次调用PUT方法之前，hashMap是没有数组和链表的，在每次put元素之后，开始检查(生成)数组和链表；

Hashtable是线程安全的，因为每个操作都加了synchronized锁，但是会导致调用Hashtable的时候，如果线程一多就会堵死。所以会有下一章ConcurrentHashMap。

转载地址：http://uqugn.baihongyu.com/