hashMap 面试题

hashMap 面试题 HashMap jdk 1.8与1.7有什么区别

1.定义
保存键值对，键不可以重复（用的Set保存）
2.底层实现
java8前：数组+链表 hash（key.hashCode()）%len 性能恶化 从O(1)变成O(n)
java8后：数组+链表+红黑树 性能从O(n)提高到O(logn)  TREEIFY_THRESHOLD 
3.元素node的组成：hash值、键、值、next
4.数组默认大小：16
什么时候变红黑树：链表大小超过8 且HashMap元素超过64（否则只会扩容）
什么时候变回链表：链表大小小于6
5.是懒加载的（lazy-load）HashMap属于懒加载，在初始化的时候没做什么动作，而是put的时候才进行扩容，然后把元素放进去

HashMap put方法里面的逻辑

诺hashMap 未被初始化 则进行初始化 *** 作 ；对key 求hash 值 依据Hash 值计算下标诺未发生碰撞 则直接放入桶中；诺发生碰撞 则以链表的方式链接到后面诺链表长度超过阀值 且hashmap 元素超过最低树化容量 则将链表转成红黑树诺节点已经存在 则用新值替换旧址诺桶满了（ 默认容量16*扩容因子0.75）就需要resize (扩容2倍后重排) 在jdk 1.8当中

hashMap get *** 作

get(key) 方法时获取key的hash值，计算 hash&(n-1) 得到在链表数组中的位置first=tab[hash&(n-1)],先判断first（即数组中的那个，看图1）的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可

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;//Entry对象数组  
        Node first,e; //在tab数组中经过散列的第一个位置  
        int n;  
        K k;  
      
    //也就是说在一条链上的hash值相同的  
        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))))//判断条件是hash值要相同，key值要相同  
                return first;  
        
            if ((e = first.next) != null) {  
                if (first instanceof TreeNode)  
                    return ((TreeNode)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;  
    }  

hashMap 如何有效减少碰撞

扰动函数 促使元素位置分布均匀 减少碰撞机率

使用final 对象 并采用合适的equals() 和hashCode() 方法

如何减少hash碰撞
防止键值改变，如果键值在放入时和获取时不同，就不能从hashmap中找到想要的对象了

hashMap 从获取hash 到散列的过程

1.计算hash
key的hashCode（）是返回int类型的散列值，而40亿的数组内存是放不下的，所以直接用这个散列值是不现实的
这里，hash值=高16位与自己做亦或，加大了低位的随机性，而且保证高低位都参与hash运算中，实际情况也表明这样是散列更均匀的做法
2.计算下标
hashmap底层数组的长度总是2的n次方！
下标=hash %长度，但是比取模效率更高（位与运算）

补充：关于2的n次方
不是传入多大就是多大，会转换成离他最接近的2的倍数的值。就是为了用与 *** 作代替取模

总结

调用hashCode 获取哈希值 h将h的高16位和低16位 做异或运算（hash=h^（h>>>16））下标=（n-1）&hash