Java 데이터 구조 HashMap 소스 코드 분석

HashMap은 Java 컬렉션 프레임워크에서 일반적으로 사용되는 데이터 구조입니다. JDK1.8 버전에서는 HashMap의 get 메소드와 put 메소드 구현이 이전과 다소 다릅니다.

기본 구조

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // ... 
    /**
     * 默认初始容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    /**
     * 默认负载因子为0.75
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 最大容量:1 << 30(2的30次方)
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 存放元素的数组,长度总是2的幂次方
     */
    transient HashMap.Node<K,V>[] table;
    /**
     * 存放键值对的数量
     */
    transient int size;
    /**
     * 扩容操作的阈值
     */
    int threshold;
    /**
     * 负载因子,用于计算阈值
     */
    final float loadFactor;
	// ...   
}

get 메소드

    /**
     * 根据key获取value,如果key不存在则返回null
     *
     * @param key
     * @return
     */
    public V get(Object key) {
        // 获取key对应的Node节点
        HashMap.Node<K, V> e;
        // 调用getNode方法查找key对应的Node节点,并将查找结果赋值给e
        // 如果e为null就返回null否则返回e节点的value
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    /**
     * 根据key的哈希值和key查找对应的Node节点
     *
     * @param hash
     * @param key
     * @return
     */
    final HashMap.Node<K, V> getNode(int hash, Object key) {
        // 定义局部变量tab,first,e,n和k
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> first, e;
        int n;
        K k;
        // 如果table数据不为null且长度大于0,且第一个Node节点不为空,则开始查找Node节点
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            // 如果第一个Node节点的哈希值与传入的hash值相等,且第一个Node节点的key和传入的key相等,则直接返回第一个Node节点
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果第一个Node节点不是要查找的Node节点,则开始遍历链表查找对应的Node节点
            if ((e = first.next) != null) {
                if (first instanceof HashMap.TreeNode)
                    // 如果第一个Node节点是红黑树节点,则调用红黑树节点的getTreeNode方法查找对应的Node节点
                    return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
                // 如果第一个Node节点不是红黑树节点,则遍历链表查找对应的Node节点
                do {
                    // 如果遍历到的Node节点的hash值与传入的hash值相等,且Node节点的key和传入的key相等,则返回对应的Node节点
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        // 如果在table数组中没有找到对应的Node节点,则返回null
        return null;
    }

get 메소드 작업 흐름은 다음과 같습니다.

• 해시 코드를 기반으로 해시 테이블에서의 위치를 ​​계산합니다. key

• 위치 탐색 연결된 목록이나 트리에서 해당 키-값 쌍을 찾습니다.

• 해당 키-값 쌍이 있으면 해당 값을 반환하고, 그렇지 않으면 null을 반환합니다

put method

    /**
     * 向HashMap中添加一个key-value键值对
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        // 根据key的哈希值和key查找对应的Node节点,并添加到HashMap中
        return putVal(hash(key), key, value, false, true);
    }
    /**
     * 根据key的hash值和key添加一个键值对到HashMap中
     *
     * @param hash
     * @param key
     * @param value
     * @param onlyIfAbsent
     * @param evict
     * @return
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // 定义局部变量tab,p,n和i
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, i;
        // 如果table数组为null或者长度为0,则先调用resize()方法初始化table数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 根据计算出来插入位置i插入新的键值对
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果插入的位置为null,则直接插入新的键值对
            tab[i] = newNode(hash, key, value, null);
        else {
            HashMap.Node<K, V> e;
            K k;
            // 如果插入的位置不为null,就遍历链表或树查找插入位置
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof HashMap.TreeNode)
                // 如果插入位置为红黑树节点,则调用putTreeVal方法插入新的键值对
                e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            else {
                // 遍历链表,查找插入位置
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // 直接在链表末尾插入新的键值对
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 如果此时链表长度大于等于8,则将链表转化为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果找到相同key,终止循环
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                // 如果存在相同key,则替换对应value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            // 如果插入后的HashMap的大小大于阈值,则调用resize方法扩容HashMap
            resize();
        afterNodeInsertion(evict);
        return null;
    }

put 메서드 작업 흐름은 다음과 같습니다.

• 키의 hashCode 값을 기반으로 해시 테이블의 위치를 ​​계산합니다.

• 위치가 비어 있으면 새 키-값 쌍을 직접 삽입합니다

• 위치가 비어 있지 않으면 위치를 순회 연결리스트나 트리에서 해당 키-값 쌍이 이미 존재하는지 확인

• 해당 키-값 쌍이 있으면 해당 값을 교체

• 해당 키-값 쌍이 없으면 새 키를 새 키-값 쌍으로 교체합니다. 값 쌍은 연결 목록의 끝에 삽입됩니다.

• 연결 목록의 길이가 임계값에 도달하면(기본값) 8), 연결리스트를 트리로 변환

• 삽입 후 HashMap의 크기가 임계값(기본 용량의 0.75)을 초과하는 경우 HashMap을 확장합니다.

• 삽입이 완료된 후 필요한 몇 가지 작업을 수행합니다. 수정 횟수 업데이트 등의 후속 작업

일반적으로 HashMap의 get 메소드와 put 메소드는 키-값 쌍 검색을 달성하기 위해 해시 알고리즘을 기반으로 하며 삽입에는 put 메소드가 필요합니다. Linked List를 트리로 변환, 확장 등을 포함한 더 많은 상황을 고려하기 위해

HashMap의 용량은 왜 항상 2의 n제곱입니까?

Java에서 HashMap의 용량은 항상 2입니다. n제곱의 이유

HashMap은 키-값 쌍을 저장하기 위해 내부적으로 배열을 사용합니다. 키-값 쌍이 추가되면 HashMap은 배열에 있는 hashCode 값을 기반으로 배열의 인덱스 위치를 계산합니다. 길이가 2의 n제곱이 아닌 경우 인덱스를 계산할 때 모듈로 연산이 필요하며 이는 HashMap의 성능에 영향을 미칩니다.

배열 길이가 2의 n제곱인 경우 비트 연산(& 연산)이 필요합니다. 또한 HashMap의 확장 연산에는 길이가 2의 n제곱이어야 하며, 이는 확장 중 계산을 단순화하고 성능을 향상시킬 수 있습니다.

또한 길이는 2의 n제곱입니다. 배열 크기의 또 다른 장점은 배열의 서로 다른 위치에서 해시 충돌 확률이 상대적으로 균등하다는 점입니다. 이는 해시 충돌 발생을 줄이고 HashMap의 효율성을 향상시킬 수 있습니다.

위 내용은 Java 데이터 구조 HashMap 소스 코드 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!