面试准备（二十）java HashMap

叁歲伎倆 2022-10-19 04:19 103阅读 0赞

为什么用红黑树

解决链表过长，查询效率过低的问题

为什么不直接使用红黑树

红黑树插入会很慢，要维护自己的结构

为什么使用红黑树的阈值是8

之所以是8，是因为Java的源码贡献者在进行大量实验发现，hash碰撞发生8次的概率已经降低到了0.00000006，几乎为不可能事件，如果真的碰撞发生了8次，那么这个时候说明由于元素本身和hash函数的原因，此次操作的hash碰撞的可能性非常大了，后序可能还会继续发生hash碰撞。所以，这个时候，就应该将链表转换为红黑树了，也就是为什么链表转红黑树的阈值是8。 最后，红黑树转链表的阈值为6，主要是因为，如果也将该阈值设置于8，那么当hash碰撞在8时，会反生链表和红黑树的不停相互激荡转换，白白浪费资源。

HashMap造成CPU百分百的问题

链表扩容时多线程线程不安全线程链表死循环

模拟HashMap

package HashMapSE;
    
    public interface Map<K, V> {
        V put(K k, V v);
        V get(K k);
        int size();
    
        interface Entry<K, V>{
            K getKey();
    
            V getValue();
        }
    
    }

package HashMapSE;
    
    public class HashMap<K,V> implements Map<K,V>{
    
        //定义数组
        private Entry<K, V> table[]=null;
        int size = 0;
    
        public HashMap(){
            this.table=new Entry[16];
        }
    
        //通过hash算法取值，获得数组下标，判断数组当前下标是否为空，不为空next链表
        @Override
        public V put(K k, V v) {
    
            int index = hash(k);
            Entry<K, V> entry = table[index];
            if(entry==null){
                //赋值给当前值
                table[index] = new Entry<>(k, v, index, null);
                size++;
            }else{
                table[index] = new Entry<>(k, v, index, entry);
            }
            return table[index].getValue();
        }
    
        private int hash(K k){
            int index = k.hashCode()%16;
            return index>=0?index:-index;
        }
    
        //取值 通过key 进行hash，判断下标位置是否为空，如果不为空依次判断
        @Override
        public V get(K k) {
            if(size==0){
                return null;
            }
            int index = hash(k);
            Entry<K, V> entry = findValue(table[index], k);
            return entry.getValue();
        }
    
    
        private Entry<K,V> findValue(Entry<K,V> entry, K k) {
            //判断当前k与要查询的k
            if(k.equals(entry.getKey())||k==entry.getKey()){
                return entry;
            }else{
                if(entry.next!=null){
                    return findValue(entry.next,k);
                }
            }
            return null;
        }
    
    
        @Override
        public int size() {
            return size;
        }
    
        class Entry<K,V> implements Map.Entry<K,V>{
            K k;
            V v;
            int hash;
            Entry<K, V> next;
    
            public Entry(K k, V v, int hash, Entry<K, V> next) {
                this.k = k;
                this.v = v;
                this.hash = hash;
                this.next = next;
            }
    
            @Override
            public K getKey() {
                return k;
            }
    
            @Override
            public V getValue() {
                return v;
            }
        }
    }