HashMap底层实现原理（增删查改）

绝地灬酷狼 2023-05-21 07:20 26阅读 0赞

### 文章目录 ###

*   *  HashMap底层实现原理（增删查改）
     *  HashMap的构造方法
     *  put方法
     *  根据key获取value
     *  删除key

## HashMap底层实现原理（增删查改） ##

## HashMap的构造方法 ##

*注意：  
不同于Java7中的构造方法，Java8对于数组table的初始化，并没有直接放在构造器中完成，而是将table数组的构造**延迟到了resize中完成***

// 构造方法一：带有初始容量的构造，负载因子使用默认值0.75
    public HashMap(int initialCapacity){
        
            this(initialCapacity,DEFAULT_LOAD_FACTOR);
            }// 构造方法二：
    public HashMap(){
        
            this.loadFactor=DEFAULT_LOAD_FACTOR; // all other fields defaulted
            }
    // 构造方法一：带有初始容量和初始负载因子的构造
    public HashMap(int initialCapacity,float loadFactor){
        
    // 如果容量小于0，抛出非法参数异常
            if(initialCapacity< 0)
            throw new IllegalArgumentException("Illegal initial capacity: "+
            initialCapacity);
    // 如果初始容量大于最大值，用2^30代替
            if(initialCapacity>MAXIMUM_CAPACITY)
            initialCapacity=MAXIMUM_CAPACITY;
    // 检测负载因子是否非法，如果负载因子小于0，或者负载因子不是浮点数，抛出非法参数异常
            if(loadFactor<=0||Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: "+
            loadFactor);
    // 给负载因子和容量赋值，并将容量提升到2的整数次幂
    // 注意：构造函数中并没有给
            this.loadFactor=loadFactor;
            this.threshold=tableSizeFor(initialCapacity);
         }

## put方法 ##

如果当前数组table为null，进行resize()初始化，否则计算数组索引 i = (n - 1) & hash  
如果这个table\[i\]值为空，那么就将这个Node键值对放在这里，判断key是否与table\[i\]重复，重复则替换，不重复在判断table\[i\]是否连接了一个链表，链表为空则new 一个Node键值对，链表不为空就循环直到最后一个节点的next为null或者出现出现重复key值

final V putVal(int hash,K key,V value,boolean onlyIfAbsent,
            boolean evict){
        
            Node<K, V>[]tab;Node<K, V> p;int n,i;
    // 1. 桶如果是空的，则进行扩容
            if((tab=table)==null||(n=tab.length)==0)
            n=(tab=resize()).length;
    // 2. (n-1)&hash-->计算桶号，如果当前桶中没有节点，直接插入
    // p来记录桶中的第一个节点
            if((p=tab[i=(n-1)&hash])==null)
            tab[i]=newNode(hash,key,value,null);
            else{
        
            Node<K, V> e;K k;
    // 3. 如果key已经是和桶中第一个节点相等，不进行插入
            if(p.hash==hash&&
            ((k=p.key)==key||(key!=null&&key.equals(k))))
            e=p;
            else if(p instanceof TreeNode) // 4. 如果该桶中挂接的是红黑树，向红黑树中插入
            e=((TreeNode<K, V>)p).putTreeVal(this,tab,hash,key,value);
            else{
        
    // 5. key不同，也不是红黑树，说明当前桶中挂的是一个链表
    // a. 在当前链表中找key
    // b. 如果找到，则不插入
    // c. 如果没有找到，先构建新节点，然后将该节点尾插到链表中
    // d. 检测bitCount的计数，binCount记录的是在未插入新节点前原链表的节点个数
    // e. 新节点插入后，链表长度是否超过TREEIFY_THRESHOLD，如果超过将链表转换为红黑树
            for(int binCount=0;;++binCount){
        
            if((e=p.next)==null){
        
    // p已经是最后一个节点，说明在链表中未找到key对应的节点
    // 进行尾插
            p.next=newNode(hash,key,value,null);
            if(binCount>=TREEIFY_THRESHOLD-1) // -1 for 1st
            treeifyBin(tab,hash); // 将链表转化为红黑树
            break;
            }
    // 如果key已经存在，跳出循环
            if(e.hash==hash&&
            ((k=e.key)==key||(key!=null&&key.equals(k))))
            break;
            p=e;
            }
            }
    // 如果key已经存在，将key所对节点中的value替换为参数指定value，返回旧value
            if(e!=null){
         // existing mapping for key
            V oldValue=e.value;
            if(!onlyIfAbsent||oldValue==null)
            e.value=value;
            afterNodeAccess(e);
            return oldValue;
            }
            }
            ++modCount;
            if(++size>threshold)
            resize();
            afterNodeInsertion(evict);
            return null;
            }
    /*
    注意：afterNodeAccess和afterNodeInsertion主要是LinkedHashMap实现的，HashMap中给出了该方法，但是
    并没有实现
    */
    // Callbacks to allow LinkedHashMap post-actions
    // 访问、插入、删除节点之后进行一些处理，
    // LinkedHashMap正是通过重写这三个方法来保证链表的插入、删除的有序性
            void afterNodeAccess(Node<K, V> p){
        }
            void afterNodeInsertion(boolean evict){
        }
            void afterNodeRemoval(Node<K, V> p){
        }
    /*
    LinkedHashMap: 继承了HashMap，在LinkedHashMap中会对以上方法进行重写，以保证存入到LinkedHashMap中的key是有序的，注意这里的有序是不自然序列，指的是插入元素的先后次序
    LinkedHashMap底层的哈希桶使用的是双向链表
    */

## 根据key获取value ##

*1. 通过key计算出其哈希地址，然后借助哈希地址在哈希桶中找到与key对应的节点  
2. 如果节点为null，返回null，说明HashMap中节点是可以为空的  
3. 如果节点不为空，返回该节点中的value*

public V get(Object key){
        
            Node<K, V> e;
            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;
    // 1. 先检测哈希桶是否为空
    // 2. 检测哈希桶的个数是否大于零，如果桶不空，桶的个数肯定不为0
    // 3. n-1&hash-->计算桶号
    // 4. 当前桶是否为空桶
    // 如果1 2 3 4均不成立，说明当前桶中有节点，拿到当前桶中第一个节点
            if((tab=table)!=null&&(n=tab.length)>0&&
            (first=tab[(n-1)&hash])!=null){
        
    // 如果节点的哈希值与key的哈希值相等，然后再检测key是否相等
    // 如果相等，则返回该节点
    // 此处也进一步证明了：HashMap必须要重载hashCode和equals方法
            if(first.hash==hash&& // always check first node
            ((k=first.key)==key||(key!=null&&key.equals(k))))
            return first;
    // 如果第一个节点后还有节点，检测first是否为treeNode类型的
    // 因为如果哈希桶中某条链节点大于8个，为了提高性能，HashMap会将链表替换为红黑树
    // 此时再红黑树中找与key对应的节点
            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;
     }

## 删除key ##

具体删除方法参考removeNode方法  
删除成功：返回与key所对应的value  
删除失败：返回null

public V remove(Object key){
        
            Node<K, V> e;
            return(e=removeNode(hash(key),key,null,false,true))==null?
            null:e.value;
            }
    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;
    // 1. 检测哈希表是否存在
    // 2. index = (n - 1) & hash: 获取桶号
    // 3. p记录当前桶中第一个节点，如果桶中没有节点，直接返回null
            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){
        
    // 如果当前桶下是红黑树，在红黑树中查找，结果用node记录
            if(p instanceof TreeNode)
            node=((TreeNode<K, V>)p).getTreeNode(hash,key);
            else{
        
    // 当前桶下是链表，遍历链表，在链表中检测是否存在为key的节点
            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不为空，在HashMap中找到了
            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
            p.next=node.next; // 非第一个节点
            ++modCount;
            --size;
    // LinkedHashMap使用
            afterNodeRemoval(node);
    // 删除成功，返回原节点
            return node;
            }
         }
    // 删除失败返回空
            return null;
         }