手撕 JDK1.8 HashMap源码（下）-白红宇

手撕 JDK1.8 HashMap源码（下）

阅读量：796 次

发布时间：2023-03-25

本文共 9270 字，大约阅读时间需要 30 分钟。

手撕 JDK1.8 HashMap 源码（下）

1. 核心常量与属性

常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始容量默认为16
static final int MAXIMUM_CAPACITY = 1 << 30;     // 最大容量为2^30
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子默认为0.75
static final int TREEIFY_THRESHOLD = 8;          // 树化阈值：链表长度达到8时会树化
static final int MIN_TREEIFY_CAPACITY = 64;     // 树化条件：表长度达到64且链表长度达到8
static final int UNTREEIFY_THRESHOLD = 6;       // 树降级为链表的阈值：链表长度达到6时会降级

Node类

static class Node
   
     implements Map.Entry
    
      {
    final int hash;
    final K key;
    final V value;
    Node
     
       next;
    
    Node(int hash, K key, V value, Node
      
        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; }
    
    public final boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Map.Entry) {
            Map.Entry
        e = (Map.Entry
       ) o;
            return Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue());
        }
        return false;
    }
}

属性

transient Node
   
    [] table;
transient Set
    
     
      > entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

2. 构造方法

双参构造方法

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);
}

单参构造方法

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

无参构造方法

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

接受Map构造方法

public HashMap(Map
   
     m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3. put() 方法

put() 总结

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal() 方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node
   
     tab[] = table;
    Node
    
      p = null;
    int n = tab.length;
    if ((tab = table) == null || n == 0) {
        table = resize();
        n = table.length;
    }
    int i = (n - 1) & hash;
    if ((p = tab[i]) == null) {
        tab[i] = new Node<>(hash, key, value, null);
    } else {
        if (p.hash == hash && 
            (key == p.key || (key != null && key.equals(p.key)))) {
            e = p;
        } else if (p instanceof TreeNode) {
            e = ((TreeNode
     
      ) p).putTreeVal(this, tab, hash, key, value);
        } else {
            for (int binCount = 0; ; binCount++) {
                if ((e = p.next) == null) {
                    p.next = new Node<>(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) {
                        treeifyBin(tab, hash);
                    }
                    break;
                }
                if (e.hash == hash && 
                    (key == e.key || (key != null && key.equals(e.key)))) {
                    break;
                }
                p = e;
            }
        }
    }
    if (e != null) {
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null) {
            e.value = value;
        }
        afterNodeAccess(e);
        return oldValue;
    }
    size++;
    if (size > threshold) resize();
    afterNodeInsertion(evict);
    return null;
}

4. resize() 扩容方法

resize() 总结

final Node
   
    [] resize() {
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        newCap = oldCap << 1;
        if (newCap > MAXIMUM_CAPACITY) newCap = MAXIMUM_CAPACITY;
        newThr = (oldThr << 1) > 0 ? oldThr << 1 : 0;
        threshold = newThr;
    } else if (oldThr > 0) {
        newCap = oldThr;
        newThr = (oldThr << 1) > 0 ? oldThr << 1 : 0;
    } else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * newCap);
        if (newThr > 0 && newThr < MAXIMUM_CAPACITY) newThr >>= 1;
    }
    if (newThr == 0) {
        newThr = (newCap < MAXIMUM_CAPACITY && (float) newCap * loadFactor < MAXIMUM_CAPACITY) ? (int)(newCap * loadFactor) : Integer.MAX_VALUE;
    }
    threshold = newThr;
    Node
    
     [] newTab = (Node
     
      []) new Node[newCap];
    if (oldTab != null) {
        for (int j = 0; j < oldCap; j++) {
            if ((e = oldTab[j]) != null) {
                if (e.next == null) {
                    newTab[e.hash & (newCap - 1)] = e;
                } else if (e instanceof TreeNode) {
                    ((TreeNode
      
       )e).split(this, newTab, j, oldCap);
                } else {
                    loHead = null;
                    loTail = null;
                    hiHead = null;
                    hiTail = null;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            loTail = loHead == null ? e : new Link(e);
                            if (loHead == null) loHead = e;
                        } else {
                            hiTail = hiHead == null ? e : new Link(e);
                            if (hiHead == null) hiHead = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    table = newTab;
    return newTab;
}

5. get() 方法

get() 总结

public V get(Object key) {
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode() 方法

final Node
   
     getNode(int hash, Object key) {
    if (tab != null && n > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((key == first.key) || (key != null && key.equals(first.key)))) {
            return first;
        }
        if ((e = first.next) != null) {
            if (first instanceof TreeNode) {
                return ((TreeNode
    
     ) first).getTreeNode(hash, key);
            } else {
                do {
                    if (e.hash == hash && ((key == e.key) || (key != null && key.equals(e.key)))) {
                        return e;
                    }
                } while ((e = e.next) != null);
            }
        }
    }
    return null;
}

6. remove() 方法

remove() 总结

public V remove(Object key) {
    return removeNode(hash(key), key, null, false, true);
}

removeNode() 方法

final Node
   
     removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    if (tab != null && n > 0 && (p = tab[index]) != null) {
        if (p.hash == hash && ((key == p.key) || (key != null && key.equals(p.key)))) {
            node = p;
        } else if ((e = p.next) != null) {
            if (p instanceof TreeNode) {
                node = ((TreeNode
    
     ) p).getTreeNode(hash, key);
            } else {
                do {
                    if (e.hash == hash && ((key == e.key) || (key != null && key.equals(e.key)))) {
                        node = e;
                        break;
                    }
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (value == node.value) || (value != null && value.equals(node.value)))) {
            if (node instanceof TreeNode) {
                ((TreeNode
     
      ) node).removeTreeNode(this, tab, movable);
            } else if (node == p) {
                tab[index] = node.next;
            } else {
                p.next = node.next;
            }
            modCount++;
            size--;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

7. replace() 方法

replace() 总结

public boolean replace(K key, V oldValue, V newValue) {
    if ((e = getNode(hash(key), key)) != null && 
        ((e.value == oldValue) || (e.value != null && e.value.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

双参replace() 方法

public V replace(K key, V value) {
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

通过对上述方法的分析，可以看出HashMap的实现细节，包括哈希计算、路由寻址、链表和树化处理、扩容机制等。这些机制共同确保了HashMap在高负载环境下的高效性能。

转载地址：http://akhfk.baihongyu.com/

你可能感兴趣的文章

Objective-C实现单向链表的反转（附完整源码）

查看>>

Objective-C实现单字母密码算法(附完整源码)

查看>>

Objective-C实现单循环链表算法（附完整源码）

查看>>

Objective-C实现单词计数(附完整源码)

查看>>

Objective-C实现单链表反转（附完整源码）