HashMap底层实现原理

爱被打了一巴掌 2024-03-23 15:29 93阅读 0赞

## Jdk8 HashMap底层实现原理 ##

### HashMap的简单的概述 ###

hashmap是一个k,v键值对型的集合，是java中常用的集合类对象，其基于哈希表的Map的接口进行实现。hashmap的实现不是同步的，这意味着它不是线程安全的。如果需要使用线程安全的k-v集合我们可以使用ConcurrentHashMap或者HashTable。hashmap的key以及value是可以为null的，但ConcurrentHashMap中是不允许key和value为null的。HashMap的映射不是有序的。jdk1.8之前HashMap有数组+链表组成，Hashmap的组成主要是由数组的形式为主，链表是为了解决hash冲突的。jdk8之后HashMap引入了红黑树，当数组中存储的数据大于数组长度\*0.75时触发数组的扩容，当数组长度大于64且链表长度大于8时再次触发其扩容机制链表将变成红黑树。红黑树结点小于6时将转换为链表。

### hash冲突以及解决方式 ###

一、 什么是hash?

Hash叫做“散列表”，就是把任意长度的输入，通过散列算法，变成固定长度输出，该输出结果是散列值。其实这种转换是一种压缩映射，散列表的空间通常小于输入的空间，不同的输入可能会散列成相同的输出，所以不能从散列表来唯一的确定输入值。这就出现了Hash冲突。

二、 什么是hash冲突?

根据key(键)即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式),但是却发现算出来的地址上已经被占用了。这就是所谓的hash冲突。

三、 解决hash冲突的方法

1.  开放定址法  
    该方法也叫做再散列法，其基本原理是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址
2.  再Hash法  
    这种方法就是同时构造多个不同的哈希函数： Hi=RH1（key） i=1，2，…，k。当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
3.  链地址法(hashmap使用方式)  
    其基本思想: 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4.  平方寻址法
    
    即是发生冲突时，用发生冲突的单元H(key), 加上 1²、 2²等，即H(key) + 1²，H(key) + 2²，H(key) + 3²…直到找到空闲单元。f(i)也可以构造为：±i^2,i=1,2,3,…,k。

### hashmap 在内存中的结构 ###

![在这里插入图片描述][34a9c35b30504f4f88feb2e9974bfc08.png_pic_center]

### hashMap 体系结构 ###

![在这里插入图片描述][9ce6f06f03e74f8a976218d7f580a94e.png_pic_center]

### 源码阶段 ###

在开启追源码之路之前先来介绍几个属性:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载因子
    static final int TREEIFY_THRESHOLD = 8; //转为树的阈值
    static final int UNTREEIFY_THRESHOLD = 6; //树退化为链表的阈值
    static final int MIN_TREEIFY_CAPACITY = 64;//数组长度转为红黑树的阈值
    static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 
    int threshold; //阈值

### 构造方法 ###

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;//根据给定的加载因子赋给成员
        this.threshold = tableSizeFor(initialCapacity); //将容量转化成2的幂的形式
     }
    public HashMap(Map<? extends K, ? extends V> m) {
        
         this.loadFactor = DEFAULT_LOAD_FACTOR;
         putMapEntries(m, false);//将传进来的map赋值给新的map
    }
    public HashMap(int initialCapacity) {
        //指定初始容量,使用默认加载因子
          this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        
         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

### 数组容量的加工 ###

//具体算法思想:对任意十进制数转换为2的整数幂，结果是这个数本身的最高有效位的前一位变成1，最高有效位以及其后的位都变为0,保证了任意十进制数转换为2的整数次幂
    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;
    }

### hash码的算法 ###

//key为空时直接返回0,如果不为空获取key的hashcode与其左移16位的值的进行异或运算,保证了高16位与低16位都参与到hash的运算当中,以减小hash冲突的可能
    static final int hash(Object key) {
        
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    //具体实例
    //如果得到两key的hashcode为以下两种,如果不进行移位,如果此时数组的长度为16,则两个key得到的位置均为10,形成hash冲突
    0000 1010 0010 1010 1010 1000  1010 1010
    0000 1010 0011 1011 1010 1000  0010 1010
    //如果按照如此上述代码方式,我们将会得到一个数组下标为0，一个数组下标为1,从一定程度上减小了hash冲突
    0000 1010 0010 1010 1010 1000  1010 1010
    0000 0000 0000 0000  0000 1010 0010 1010
    ----------------------------------------
    0000 1010 0010 1010 1010 0010 1000 0000
        
    0000 1010 0011 1011 1010 1000  0010 1010
    0000 0000 0000 0000 0000 1010 0011 1011
    ------------------------------------------
    0000 1010 0011 1011 1010 0010 0001 0001

### putVal(put方法添加) ###

//jdk 1.8
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //判断当前数组是否初始化
            if ((tab = table) == null || (n = tab.length) == 0)
                //没有初始化就去初始化
                n = (tab = resize()).length;
            //通过hash值与数组长度相与得到元素存放的数组下标,如果该位置为空直接添加结点,如果不为空则出现哈希冲突,利用拉链法将结点利用尾插的方式插入
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
        
                Node<K,V> e; K k;
                if (p.hash == hash && //如果两个节点的key相同直接替换
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)//如果当前节点已经为红黑树则采用树的添加方式进行添加
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        //如果为链表，则采用尾插的方式,如果链表长度大于8则会调用treeifyBin方法进行扩容
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);//尾插
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果链表长度大于转为红黑树的阈值将进行对数组扩容或者转为红黑树
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash && 判断链表中是否有重复值
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //判断是否有重复key,替换旧值
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //迭代器的failfast机制
            //在HashMap使用迭代器时，在remove、put元素的时候可能会导致迭代器中的内容数据破坏，
            ++modCount;
            //判断一下当前的HashMap容量是否已经达到扩容的阈值,达到阈值进行扩容
            if (++size > threshold) 
                resize();
            afterNodeInsertion(evict);
            return null;
        }

### treeifyBin ###

主要工作：

1.  对数组进行扩容
2.  满足转换红黑树的条件时进行转换

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//如果数组长度小于64则对数组进行扩容
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
        //否者将转为红黑树
            TreeNode<K,V> hd = null, tl = null;
            do {
        
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
        
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

### resize方法(扩容) ###

主要分为两大步：

1.  根据不同的情况进行对容量和阈值进行扩大
2.  将原来数组的中的元素转移到新的数组当中

//第一步:根据不同的情况对其的容量阈值进行扩大
    final Node<K,V>[] resize() {
        
        //将table中的值和数据保存下来
        Node<K,V>[] oldTab = table;
        //检查其数组的长度，是已经初始化过的还是没有被初始化的
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //旧值的阈值
        int oldThr = threshold;
        int newCap = 0;//新的容量 
             newThr = 0;//新的阈值
        if (oldCap > 0) {
        
            if (oldCap >= MAXIMUM_CAPACITY) {
        //如果当前容量已经大于MAXIMUM_CAPACITY则修改阈值为Integer.MAX_VALUE直接返回即可
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }//否则将原来的容量扩大两倍并且大于默认容量时将阈值扩大原来的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //若没有经历过初始化，并且在使用时通过构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        
        //若没有被初始化过则采用默认的容量16 以及阈值12
        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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新容量的数组
         //将新建立数组赋值到HashMap成员变量
        table = newTab;
        if (oldTab != null) {
        
            for (int j = 0; j < oldCap; ++j) {
        
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
        
                    //将旧数组[j]处置为空
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;//重新计算在新数组中的位置
                    else if (e instanceof TreeNode)//如果该节点为红黑树结点则根据红黑树进行转换
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
         // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> 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;               
                        }
                    }
      //解释一下:为什么是j和j+oldcap的位置？            
      //如果原始数组长度16则新数组的长度必然为32,根据hash值计算在数组中存放的位置为(n-1)&hash 
      //原始数组 最后决定位置的参考值为最后4位
      //扩容之后 最后决定位置的参数值为最后5位
      //其实也就是说如果倒数第五位为0时即在原来位置,如果该位为1时即为原来位置+原来数组长度 
      //其实这样说来就是if语句中条件判断的来源了                 
                }
            }
        }
        return newTab;
    }

### removeNode(删除) ###

主要三大步：

1.  根据不同的情况查找到对应的结点
2.  再根据不同的情况进行移除
3.  修改其大小

//     * @param matchValue if true only remove if value is equal
    //   * @param movable if false do not move other nodes while removing
    final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
        
        Node<K,V>[] tab; Node<K,V> p; 
        int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
        
             Node<K,V> node = null, e; K k; V v;
             if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;//如果通过hash直接找到对应数组元素,则把p赋给node
              else if ((e = p.next) != null) {
        //如果该结点下为链表或红黑树
                if (p instanceof TreeNode)
                   node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//在红黑树中寻找待删除结点
                 else {
        //如果为链表
                    do {
        
                      if (e.hash == hash &&
                         ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
        
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                //如果node不为空说明找到了要删除的Node节点
                //并且matchValue为false
                //或者matchValue为true，并且node的value等于参数中的value
                //或者matchValue为true，并且value放法的equals返回true
                //则可以执行删除操作
    
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
        
                    if (node instanceof TreeNode)//如果为红黑树结点则采用树删除结点的方式
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p) //该节点为链表的第一个结点则直接下移
                        tab[index] = node.next;
                    else //如果既不是treenode类型，又等于节点p就修改链表使p的后继节点等于node的后继节点
                        p.next = node.next;
                    //将修改次数++
                    ++modCount;
                    --size;//将size--
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

### getNode(查找) ###

final Node<K,V> getNode(int hash, Object key) {
        
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        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) {
        
                if (first instanceof TreeNode)//如果为树则利用树的形式进行查找
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
        //如果不是树,则利用链表的形式
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

### 面试官爱问的问题 ###

1.  hashMap的底层数据结构
    
    1.  jdk 1.8 采用数组+链表+红黑树的方式
    2.  jdk 1.8之前采用数组+链表
    
    当链表过长，则会严重影响HashMap的性能，红黑树搜索时间复杂度是O(logn)，而链表是O(n)。因此，JDK1.8对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
    
    当链表超过8且数组长度(数据总量)超过64才会转为红黑树
    
    将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
2.  hashmap的特点
    
    1.  hashmap存取是无序的
    2.  键和值位置都可以是null，但是键位置只能是一个null
    3.  键位置是唯一的，底层的数据结构是控制键的
    4.  jdk1.8前数据结构是：链表+数组jdk1.8之后是：数组+链表+红黑树
    5.  阈值（边界值）>8并且数组长度大于64，才将链表转换成红黑树，变成红黑树的目的是提高搜索速度，高效查询
3.  解决hash冲突方法有哪些？hashmap中用的哪种？
    
    1.  开放定址法  
        该方法也叫做再散列法，其基本原理是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址
    2.  再Hash法  
        这种方法就是同时构造多个不同的哈希函数： Hi=RH1（key） i=1，2，…，k。当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
    3.  链地址法(hashmap使用方式)  
        其基本思想: 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
    4.  平方寻址法
        
        即是发生冲突时，用发生冲突的单元H(key), 加上 1²、 2²等，即H(key) + 1²，H(key) + 2²，H(key) + 3²…直到找到空闲单元。f(i)也可以构造为：±i^2,i=1,2,3,…,k。
        
        在hashmap中使用了拉链寻址法(即链式寻址法)
4.  为什么hashmap中数组长度大于64之后，链表长度大于8之后才转换为红黑树？
    
    1.  我们都知道数组是可以通过下标直接访问的，即时间复杂度为O(1),而链表的查询的时间复杂度为O(N),红黑树的查询的时间复杂度为O(logn)
    2.  虽然红黑树的查询速度是相比链表来说是比较高的，但是转换为红黑树的过程是非常费时间和空间的
    3.  经过官方的测试hash冲突是很少会出现8次以上的，从官方来讲也是不太想去将其转换为树结构的
    4.  就数组为什么要扩展到64就源码注释来说是为了防止数组的长度大小的改变来引起树化，简单来说就是防止多次链表和树的转换
5.  为什么重写equals方法要重写hashcode方法
    
    1.  equals 方法和 hashCode 方法是 Object 类中的两个基础方法，它们共同协作来判断两个对象是否相等。
    2.  如果只重写了 equals 方法，那么默认情况下，Set 进行去重操作时，会先判断两个对象的 hashCode 是否相同，此时因为没有重写 hashCode 方法，所以会直接执行 Object 中的 hashCode 方法，而 Object 中的hashCode 方法对比的是两个不同引用地址的对象，所以结果是 false，那么 equals 方法就不用执行了，直接返回的结果就是 false：两个对象不是相等的，于是就在 Set 集合中插入了两个相同的对象。
    3.  但是，如果在重写 equals 方法时，也重写了 hashCode 方法，那么在执行判断时会去执行重写的 hashCode 方法，此时对比的是两个对象的所有属性的 hashCode 是否相同，于是调用 hashCode 返回的结果就是 true，再去调用 equals 方法，发现两个对象确实是相等的，于是就返回 true 了，因此 Set 集合就不会存储两个一模一样的数据了，于是整个程序的执行就正常了。
    
    总结 hashCode 和 equals 两个方法是用来协同判断两个对象是否相等的，采用这种方式的原因是可以提高程序插入和查询的速度，如果在重写 equals 时，不重写 hashCode，就会导致在某些场景下，例如将两个相等的自定义对象存储在 Set 集合时，就会出现程序执行的异常，为了保证程序的正常执行，所以我们就需要在重写 equals 时，也一并重写 hashCode 方法才行。
6.  hashMap中的容量为什么要保证是2的n次幂
    
    其的主要目的还是为了减小hash冲突的可能,当容量为2的整数幂次时在计算在数组中的位置时，与hash进行与运算(n-1)&hash,n-1保证左边为1111这样的二进制数字,做与运算的规则为有0则为0,全1才为1，这在一定程度上极大的减小了hash冲突的可能。
7.  加载因子为什么为0.75
    
    loadFactory越趋近于1，那么数组中存放的数据（entry也就越来越多），数据也就越密集，也就会有更多的链表长度处于更长的数值，我们的查询效率就会越低，添加数据时，产生hash冲突的概率也会更高
    
    默认的loadFactory是0.75，loadFactory越小，越趋近于0，数组中个存放的数据(entry)也就越少，表现得更加稀疏
    
    0.75是对空间和时间效率的一种平衡选择
    
    如果负载因子小一些比如是0.4，那么初始长度16\*0.4=6，数组占满6个空间就进行扩容，很多空间可能元素很少甚至没有元素，会造成大量的空间被浪费
    
    如果负载因子大一些比如是0.9，这样会导致扩容之前查找元素的效率非常低
    
    就0.75并不一定非要使用他，可以根据自己的数据的需求去适当改变，只是一种比较好的建议。
8.  一般用什么作为hashmap中的key？
    
    一般情况下会选择不可变的值或对象作为Map中的key，其实一切对象都可以作为Key值。如：Integer、Long、String、Object等。但是在实际工作中，最常用的使用String作为Key值。
    
    主要原因如下:
    
    1.  使用Object作为Key值的时候，如class Person (里面包含，姓名，年龄，性别，电话等属性)作为Key。当Person类中的属性改变时，导致hashCode的值也发生变化，变化后，map.get(key)因为hashCode值的变化，而无法找到之前保存的value值，同样，删除也取不到值。解决方案是重写HashCode方法
    2.  避免使用Long，Integer做key。由于拆箱装箱的过程将可能创建新的对象，导致取不到数据。
9.  hashmap为什么线程不安全？
    
    首先我们通过看hashmap的源码，其中的相关方法从hashmap的插值、移除元素、以及查找等一系写的方法都没有对其有线程安全的处理。自然也就线程不安全了。
    
    在多线程高并发的情况下任意一条语句都有可能被cpu执行，这就很难去保证线程的安全，数据的不丢失问题了
10. 为什么在计算hash值时为什么要让低16位和高16位进行异或处理(见上述hash值的计算)
11. hashmap中为什么选用红黑树而没有选用avl树
    
    1.  红黑树和AVL树都是最常用的平衡二叉搜索树，它们的查找、删除、修改都是O(logn)
    2.  Avl是严格的平衡查找树，因此可以提供更快的查找速度，一般使用在读取查找密集型任务，但由于其的条件相对来说是比较苛刻的(从根到任何叶子的最短路径和最长路径之间的差异最多为1),这就对于添加和删除是很不友好的，真是因为其的严格平衡性，有可能因为添加和删除操作就会导致树进行左旋或者右旋操作，变得没有那么不在节省时间。但对红黑树来说就没那么严苛，从根到任何叶子的最短路径和最长路径之间的差异最多可以为2，相对来说这就会使得左旋以及右旋的操作变得少一些。
    3.  就实际操作来说Avl树对平衡的调节上是比较麻烦的且是不太好操作的
12. hashmap如何进行遍历
    
    就实际和普遍使用来说hashmap有两种遍历方式
    
    1.  利用EntrySet对象进行遍历
        
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                    
            	System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
            }
    2.  利用keyset获取到对应的key通过key得到具体的vlue进行遍历
        
            for (Integer key : map.keySet()) {
                    
            	System.out.println("Key = " + key);
            }
    3.  利用迭代器进行遍历
        
            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());
             }
            Iterator<Map.Entry> entries = map.entrySet().iterator();
                while (entries.hasNext()) {
                    
            	    Map.Entry entry = (Map.Entry) entries.next();
            		Integer key = (Integer) entry.getKey();
            		Integer value = (Integer) entry.getValue();
            		System.out.println("Key = " + key + ", Value = " + value);
            }
    4.  利用jdk8新特性进行遍历
        
            map.forEach((k, v) -> System.out.println("key: " + k + " value:" + v));
13. HashMap的最大容量为什么是2的30次方(1左移30)?
    
    在java中int类型为有符号的整形即最高位为符号位,符号位为1时代表该数为负数,int类型在java中占用4个字节即32位,1>>30位之后，其实已经占用了31位,如果再进行移位将变成负值,无法作为容量进行操作。
14. HashMap初始化容量，设置多少合适。
    
    我们知道创建一个HashMap对象如果不指定初始化容量initialCapacity的话，HashMap的默认容量是16，但在阿里手册上这样写着建议使用下面的方式进行初始化，但这个初始化容量应该如何去填写呢？真的是需要多少创建多少吗？比如说我现在需要7个空间,就要传一个7吗？其实并非这样，当我们将初始容量传入7时实际上jdk会将容量改为8,也就是距离7最小的2的整数幂次，这样算来如果乘以加载因子0.75的话，我们只能往里面添加6个数据,如果在想添加将会触发扩容机制，其实我们知道扩容是一个很费时间以及内存的一件事情，所以要7个元素的空间传7并不是一个好的选择，所以阿里规范中提出了 expectedSize / 0.75F + 1.0F;这样得出的结果为10，最终我们将会得到一个16容量的map集合，可以添加的元素个数为12个,虽然在一定程度上浪费了空间,但减少了一次扩容,如果我们的数据量比较大，在没有进行对hashmap进行初始化容量设置的话,使用默认值给定的16这将会导致n多次的扩容，这就会导致大量的时间以及内存浪费在上面。
    
        public HashMap(int initialCapacity) {
              //指定初始容量,使用默认加载因子
              this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

样写着建议使用下面的方式进行初始化，但这个初始化容量应该如何去填写呢？真的是需要多少创建多少吗？比如说我现在需要7个空间,就要传一个7吗？其实并非这样，当我们将初始容量传入7时实际上jdk会将容量改为8,也就是距离7最小的2的整数幂次，这样算来如果乘以加载因子0.75的话，我们只能往里面添加6个数据,如果在想添加将会触发扩容机制，其实我们知道扩容是一个很费时间以及内存的一件事情，所以要7个元素的空间传7并不是一个好的选择，所以阿里规范中提出了 expectedSize / 0.75F + 1.0F;这样得出的结果为10，最终我们将会得到一个16容量的map集合，可以添加的元素个数为12个,虽然在一定程度上浪费了空间,但减少了一次扩容,如果我们的数据量比较大，在没有进行对hashmap进行初始化容量设置的话,使用默认值给定的16这将会导致n多次的扩容，这就会导致大量的时间以及内存浪费在上面。

```java
    public HashMap(int initialCapacity) {//指定初始容量,使用默认加载因子
          this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    ```

[34a9c35b30504f4f88feb2e9974bfc08.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/bb1a095166984eceb94dfe5b3d45a5fe.png
[9ce6f06f03e74f8a976218d7f580a94e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2214f85ed9a04c019b3bf565b44332c5.png