深度解析HashMap集合底层原理

目录

• 前置知识
  • ==和equals的区别
  • 为什么要重写equals和HashCode
  • 时间复杂度
  • (不带符号右移) >>>
  • ^异或运算
  • &（与运算）
  • 位移操作：1<<2=4，1左移两位为什么等于4
• HashMap集合特点及源码分析（JDK1.8）
  • HashMap重要的五大点
    • 1.集合初始化
      • HashMap成员变量
      • HashMap内部数据结构
        • 链表
        • 红黑树
      • HashMap构造方法
        • 指定初始容量
        • 指定填充比
        • 用来初始化的Map
    • 2.数据寻址Get
    • 3.数据存储Put
    • 4.节点删除
    • 5.扩容原理
      • JDK1.7 HashMap中扩容机制resize()
        • 多线程环境下扩容造成死循环的分析过程
        • 解决办法
      • JDK1.8 HashMap中扩容机制resize()
• HashMap面试题
  • HashMap什么时候会转换为红黑树
  • HashMap为什么要引进红黑树，为了解决什么问题？
  • HashMap的长度为什么必须是2的次幂？
  • 如何避免HashMap内存溢出问题
  • HashMap根据key查询的时间复杂度
  • HashMapKey为null存放在什么位置
  • HashMap底层是采用单链表还是双链表
  • HashMap底层是有序存放的吗
  • LinkedHashMap 和 TreeMap底层如何实现有序的
  • 为什么HashMap不使用取模运算
  • 求下标i=(n-1)&hash,为什么（n-1）变成了奇数
  • HashMap如何降低Hash冲突
  • 加载因子为什么是0.75而不是1
  • Hashap存放1W条数据怎么样效率最高
  • Hashmap1.7和Hashmap1.8的区别

前置知识

==和equals的区别

对于基本类型变量来说，只能使用 == ，因为基本类型的变量没有方法。使用==比较是值比较

对于引用类型的变量来说，==比较的两个引用对象的地址是否相等。所有类都是继承objcet类，而object类是equals方法比较的也是对象的地址是否相等，如果类没有重写equals方法，使用 == 和equals方法效果是一样的

为什么要重写equals和HashCode

HashCode方法：底层采用C语言编写，根据对象地址转换为整数类型

如果两个对象的HashCode相等，对象的内容至不一定相等；hash碰撞的问题

如果使用equals方法比较两个对象内容值相等的情况下，那么hashcode的值也相等

因为equals默认情况下Object类采用==比较对象，那么比较的是内存地址是否相等，当数据类型只要不是基本类型，那么比较永远不会相等。

set集合存储的就是不重复的对象，底层就是hashmap，依据equals和hashcode进行判断

时间复杂度

时间复杂度为O(n) 从头查询到尾部，查询多次

时间复杂度为O(1) 查询一次 比如根据数组下标查询

时间复杂度为O(logn) 平方查询 比如红黑树，

效率：O(1)>O(logn)>O(n)

(不带符号右移) >>>

无符号右移就是右移之后，无论该数为正还是为负，右移之后左边都是补上0

无符号右移运算符和右移运算符的主要区别在于负数的计算，因为无符号右移是高位补0，移多少位补多少个0

15>>>2=0000 1111 右移两位=0000 0011=3

^异或运算

相同为0，不同为1

2^3= 0010^0011=0001=1

&（与运算）

00得0 11得1 01得0

2&3=0010&0011=0010=2

位移操作：1<<2=4，1左移两位为什么等于4

这里的1是十进制，而计算机交流是用二进制，所以先要将1用二进制表示出来。

每一个符号（英文、数字或符号等）都会占用1Bytes的记录，每一个中文占2Byte

而一个1Bytes占8个bit，也就是8个二进制位

8位二进制数：2⁸种不同状态 0000 0000 ~1111 1111=0~255=2⁸=256

1的二进制表示0000 0001，然后进行位移操作。

位移操作向左边位移，后面空出来的补上0，越往左边越大，把0000 0001向左位移2位，变成了0000 0100，二进制0000 0100转化十进制所以为4，也可以说每左移一位是乘以2

8>>2?

0000 1000右移2位0000 0010，转化为10进制等于2

10>>2?

0000 1010右移2位0000 0010，转化为10进制等于2

1<<30?

0000 0001左移30位01000000 00000000 00000000 00000000，转化为10进制等于1073741824，也就是2³⁰

HashMap集合特点及源码分析（JDK1.8）

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

HashMap继承了AbstractMap类，实现了Cloneable克隆接口、Serializable序列化接口、Map接口

特点：数组+链表+红黑树构成

HashMap重要的五大点

1.集合初始化

HashMap成员变量

//默认初始化hashmap容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //2的4次幂  16
//hashmap最大容量1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;//2的30次幂
//扩容因子 16*0.75=12 达到12就会进行扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表中存储元素的数量 > 8 时，会自动转换为红黑树
static final int TREEIFY_THRESHOLD = 8;
//删除元素时，如果一个红黑树中中存储元素数量 < 6 后，会自动转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
//数组容量>64&链表长度>8 转为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;

//阙值，用于判断是否扩容，threshold=容量*扩容因子=16*0.75=12
int threshold;
//扩容因子实际大小
final float loadFactor;
//HashMap中元素的数量 transient表示不能被序列化
transient int size;
//集合修改次数  防止多线程篡改数据
transient int modCount;
//存储元素的数组  单向链表
transient Node<K,V>[] table;

HashMap内部数据结构

链表

//单向链表 实现了Entry接口  由上面的数组构成了数组加链表的结构
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    //构造一个节点
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    //基本方法
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
   //比较两个Node是否相等
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

红黑树

//红黑树结构概览
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;//左子树
    TreeNode<K,V> right;//右子树
    TreeNode<K,V> prev;    //
    boolean red;//是否红色
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

  //返回当前节点
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

HashMap构造方法

指定初始容量

构造一个具有默认初始容量 (16) 和默认负载因子 (0.75)的空HashMap

static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; //扩容因子0.75
}

指定填充比

构造一个具有指定初始容量和默认扩容因子 (0.75)的空HashMap

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);//初始容量  扩容因子默认0.75
}
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);
}

//获得的是大于cap的最小的2的幂，例如10，10的最小的2的幂=16
static final int tableSizeFor(int cap) {
        int n = cap - 1;//n=9   0000 1001
        n |= n >>> 1;//|= 代表异或运算  先向右位移1位=0000 0100，0000 1001和0000 0100异或运算得到0000 1101
        n |= n >>> 2;//....以此类推
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
    //n<0返回1，否则n大于MAXIMUM_CAPACITY的话返回最大值，小于最大值返回n + 1，全1的情况+1一定变成1后面跟一堆0的情况，这样就确定了最终的值，当HashMap的size到达threshold这个阈值时会扩容
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

用来初始化的Map

使用与指定Map相同的映射构造一个新的HashMap

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;//默认负载因子0.75
    putMapEntries(m, false);
}
//将集合元素put到HashMap中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    //获取元素大小
    int s = m.size();
    if (s > 0) {
        //如果存储元素的数组为空  说明这是刚构造的HashMap 那么就要为它指定最大容量
        if (table == null) {
            //根据阈值和Map大小 推算出最大容量，向上取整为了取整数
            float ft = ((float)s / loadFactor) + 1.0F;
            //判断容量是否超过最大容量 不超过就直接赋值
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            //如果容量大于阈值
            if (t > threshold)
                //重新计算阈值
                threshold = tableSizeFor(t);
        }
        //数组已经初始化了
        else if (s > threshold)
            resize(); //先扩容
        // 循环put
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            //可能会触发resize
            putVal(hash(key), key, value, false, evict);
        }
    }
}

2.数据寻址Get

根据key获取元素

public V get(Object key) {
    Node<K,V> e;
    //key的hash值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

详细方法

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab;
        Node<K,V> first, e;
        int n; K k;
     //如果table不等于null  数组不等于null   first=赋值计算当前节点的hash值所在的数组下标位置
        if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
            //如果比较当前节点的和第一个节点
            if (first.hash == hash &&((k = first.key) == key || (key != null && key.equals(k))))
                //返回第一个结点
                return first;
            //如果第一个节点的下一个节点不为null
            if ((e = first.next) != null) {
                //判断是否为红黑树
                if (first instanceof TreeNode)
                    //处理getTreeNode()方法搜索key
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //是链表
                do {
                  //遍历比较直到找到节点或者节点为null退出循环
                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

3.数据存储Put

将元素添加进HashMap

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<K,V>[] tab;
        Node<K,V> p;
        //n表示table数组的长度  i表示key存放在哪个数组下标
        int n, i;
      //将全局table=tab判断是否为空 或者 tab长度为0情况下 对table进行扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            //扩容 n=16
            n = (tab = resize()).length;
       //i = (n - 1) & hash 计算key对应的index值  tab[i]key在数组中是否存在
        if ((p = tab[i = (n - 1) & hash]) == null)
           //如果key的index值没有发生冲突
            tab[i] = newNode(hash, key, value, null);
     //key的index发生冲突了
        else {
            Node<K,V> e; K k;
            //如果hash和equals比较都相同    直接覆盖
            if (p.hash == hash &&((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 {
                //循环遍历链表
                for (int binCount = 0; ; ++binCount) {
                    //如果链表为空 直接追加在next后面
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //如果链表长度binCount大于8 数组容量大于64
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            //把链表转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    //查询链表中是否存在该key，如果存在直接修改value值
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //真正给e赋值 将新的value覆盖为oldvalue
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
       //只有新增才会使modCount++  修改不会  fastclass机制防止在做遍历的时候有集合修改类
        ++modCount;
       //如果size>12 就会提前去扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

4.节点删除

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
    }

详细方法

//hash:key的hash值  key:要删除的键值对的key    value:要删除的键值对的value
//matchValue 如果为true，则当key对应的键值对的值equals(value)为true时才删除；否则不关心value的值
//movable 删除后是否移动节点，如果为false，则不移动
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;
    //节点数组tab不为空、数组长度n大于0、根据hash定位到的节点对象p
        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;
            //如果当前节点的键和key相等，那么当前节点就是要删除的节点，赋值给node
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //获取当前节点的下一个节点
            else if ((e = p.next) != null) {
                //如果是一个红黑树，那么调用getTreeNode方法从树结构中查找满足条件的节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                //如果是链表
                else {
                    //从头到尾逐个节点比对
                    do {
                        //e节点的键是否和key相等，e节点就是要删除的节点，赋值给node变量
                        if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;//p指向e，让p存储的永远下一次循环里e的父节点
                    } while ((e = e.next) != null);
                }
            }
            //node不为空 找到了删除的节点 如果不需要对比value值或者需要对比value值但是value值也相等
            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);
                //如果是链表 该node节点就是首节点
                else if (node == p)
                    //删除 把当前节点的下一个赋值给当前表索引
                    tab[index] = node.next;
                //不是首节点，p是node的父节点
                else
                    // 删除 父节点的下一个节点就是node的下一个节点
                    p.next = node.next;
                ++modCount;//HashMap的修改次数递增
                --size;//HashMap的元素个数
                afterNodeRemoval(node);//保留的重写方法 无效果
                return node;//返回删除结果
            }
        }
        return null;
    }

5.扩容原理

JDK1.7 HashMap中扩容机制resize()

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //如果旧容量已经达到了最大，将阈值设置为最大值，与1.8相同
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //创建新哈希表
        Entry[] newTable = new Entry[newCapacity];
        //将旧表的数据转移到新的哈希表
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        //更新阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历原来数组中所有的链表
        for (Entry<K,V> e : table) {
            //判断每个下标对应的链表存放是否为空
            while(null != e) {
                //这里两个多线程环境下都拿到 e.next可能会有死循环问题
                Entry<K,V> next = e.next;
                //是否需要重新计算hash值
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //得到新表中的索引
                int i = indexFor(e.hash, newCapacity);
                //将新节点作为头节点添加到桶中
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

多线程环境下扩容造成死循环的分析过程

     for (Entry<K,V> e : table) {
          while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
     }

因为是采用头插法，会导致整个链表顺序颠倒，多线程环境下遍历table这就容易导致死循环，因为操纵的同一个e对象

在多线程同时扩容的情况下，线程一抢先获得CPU资源，而线程二被挂起，此时它们拿到的数据都是e=a；next=c；线程一率先执行把key计算好了并放入newTable了

这时候线程二又被唤醒，因为线程之间不是共享的，所以此时newTable也为空，需要重新给里面赋值，但是e变量是可以被共享的。

1、线程二第一次循环还是之前拿到的数据e=a；next=c，此时newTable还为空

// e=a  e.next=c
Entry<K,V> next = e.next;
//1
int i = indexFor(e.hash, newCapacity);
//e.next=null
e.next = newTable[i];
//数组1位置第一个元素赋值为 a
newTable[i] = e;
//e=c
e = next;

2、线程二第二次循环

第二次循环获取e的数据，因为e的之前被线程一修改过变为d->c->

// e=c   e.next=a
Entry<K,V> next = e.next;
//1
int i = indexFor(e.hash, newCapacity);
//e.next=null
e.next = newTable[i];
//数组1位置赋值为 c
newTable[i] = e;
//e=a
e = next;

因为e的之前被线程一修改过变为d->c->a，所以c.next等于线程一里面的值，c.next=a

3、线程二第三次循环

//e=a；  e.next=a.next=null
Entry<K,V> next = e.next;
//1
int i = indexFor(e.hash, newCapacity);
//此时newTable[i]=a->c  e.next=a.next   a.next=c->a 出现死循环
e.next = newTable[i];
//数组1位置赋值为 a
newTable[i] = e;
//e=null
e = next;

此时进入环形引用，无限循环中导致CPU使用率飙升

解决办法

单线程下没有不会有问题，多线程下采用ConCurrentHashMap

JDK1.8 HashMap中扩容机制resize()

 final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
       //如果原来的table=null, 则为HashMap的初始化, 生成空table返回即可
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //hashmap下一次扩容的阈值
        int oldThr = threshold;
        //记录新的容量和新的下一次扩容大小
        int newCap, newThr = 0;
        //大于0说明之前HashMap的数组不是空的
        if (oldCap > 0) {
            // 再对数组进行检测 如果大于最大容量2的30次幂 直接返回
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //否者进行扩容为之前的二倍基于右移 newCap是oldCap长度的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //下一次提前扩容的数量
                newThr = oldThr << 1;
        }
        //阈值大于0 说明集合已存在  赋值给newCap
        else if (oldThr > 0)
            newCap = oldThr;
        //如果等于0 说明刚初始化  newCap=0.75  newThr=新扩容的阈值=0.75*默认容量大小
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
       //如果下一次提前扩容的数量==0
        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"})
          //HashMap里面新的扩容容量
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
      //如果原表不为空，把原表中数据移动到新表中
        if (oldTab != null) {
            //遍历原来的列表
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //判断每个数组里面是否有链表   有的话用一个链表e存起来
                if ((e = oldTab[j]) != null) {
                    //然后将原来的链表赋值为null  能避免死循环
                    oldTab[j] = null;
                    //下一个节点为空 说明只包含一个元素
                    if (e.next == null)
                        //计算e在新table中的位置,放入其中
                        newTab[e.hash & (newCap - 1)] = e;
                    //判断当前node是否是红黑树
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //链表情况下
                    else {
                        //hashmap扩容会把原来的链表拆分成 两个链表
                        //低位链表的头尾
                        Node<K,V> loHead = null, loTail = null;
                        //高位链表的头尾
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //循环把链表拆分 放到两个链表里面
                        do {
                            next = e.next;
                            //散列下标不变的情况  oldCap=16
                            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;
                        }
                        //放在新表j+oldCap位置
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

HashMap1.8将链表通过运算拆封成两个链表存放到新的table中

HashMap面试题

HashMap什么时候会转换为红黑树

数组容量大于64并且链表长度大于8时

HashMap为什么要引进红黑树，为了解决什么问题？

链表查询时间复杂度为O(n),查询效率太低了，引用红黑树查询效率可以变为O(logN)

HashMap的长度为什么必须是2的次幂？

这样长度一定是偶数，在计算index下标的时候(n-1)&hash，这样（n-1）就会是奇数，奇数&hash值才会减小冲突。n取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列

如何避免HashMap内存溢出问题

因为没有重写hashcode和equals和方法，底层默认用==比较内存地址，就会导致new出多个对象，重写之后每次比较都会是同一个对象，会做覆盖。

HashMap根据key查询的时间复杂度

如果key没有产生冲突，时间复杂度为O(1)，一次就能查到

如果key产生冲突链表存放为O(n)，红黑树存放为O(logn)

HashMapKey为null存放在什么位置

第0个位置

int index = k == null ? 0 : k.hashCode() % objects.length;

HashMap底层是采用单链表还是双链表

单向链表

HashMap底层是有序存放的吗

单向链表存放无序散列，会将所有链表和红黑树都遍历，效率非常低

LinkedHashMap 和 TreeMap底层如何实现有序的

原理：将每个index中的链表实现关联，效率比HashMap要低

缓存淘汰算法底层实现原理LinkedHashMap

Redis如果缓存满的情况下如何清理？

LUR算法:清理最近少用的key

方案1：对每个key记录使用次数，然后排序再删除 效率非常低

方案2：基于LinkedHashMap有序集合实现 访问key的时候就会将key存到链表最后的位置

插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序

执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。

其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序。

为什么HashMap不使用取模运算

k.hashcode()%entrys.length取模会导致key冲突概率非常大

就会导致变为链表O(n)或者红黑树O(logn),需要降低Hash冲突概率，均匀的放在数组的每个下标的位置

求下标i=(n-1)&hash,为什么（n-1）变成了奇数

扩容默认是偶数，2的n次幂。如果是偶数&（与运算）hash，index冲突概率非常大，会使数据分布不均

所以需要变成奇数

HashMap如何降低Hash冲突

hash函数计算i=(n-1)&hash,通过奇数余hash值能够降低hash值发生冲突的概率

加载因子为什么是0.75而不是1

如果加载因子越大（1），空间利用率比较高16个位置都填满了，这样index冲突概率比较大

如果加载因子越小（0.1），达到0.1就扩容那么空间利用率越小，能存放的位置更多，这样index冲突概率越小

空间和时间上的平衡点：0.75

统计学概率：泊松分布是统计学和概率学常见的离散概率分布

Hashap存放1W条数据怎么样效率最高

hashmap容量=（需要存储的元素个数/扩容因子）+1=（10000/0.75）+1=13334

目的是减少底层扩容的次数，如果没有设置初始容量大小，hashmap需要进行7次扩容，严重影响性能

Hashmap1.7和Hashmap1.8的区别

Hashmap1.7基于数组+链表实现头插法，写法简单 但是有多线程死循环问题

Hashmap1.8基于数组+链表+红黑树实现尾插法，解决了多线程死循环问题

能够降低key对应的index的冲突概率，提高查询率

原来的链表使用与运算hash&原来table长度，拆分成两个链表放到新数组中，能够将链表长度缩短，提高查询效率