집 >Java >java지도 시간 >Java에서 HashMap의 구현 원리 분석

Java에서 HashMap의 구현 원리 분석

不言원래의: 2018-09-11 13:57:061617검색

이 기사의 내용은 Java에서 HashMap의 구현 원리를 분석한 내용입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

1. 해시맵 개요:
HashMap은 해시 테이블을 기반으로 하는 Map 인터페이스의 비동기 구현입니다. 이 구현은 모든 선택적 매핑 작업을 제공하고 null 값과 null 키를 허용합니다. 이 클래스는 매핑의 순서를 보장하지 않으며, 특히 순서가 불변임을 보장하지 않습니다.
2. HashMap 데이터 구조:
Java 프로그래밍 언어에는 가장 기본적인 두 가지 구조가 있는데 하나는 배열이고 다른 하나는 시뮬레이션된 포인터(참조)입니다. 이 두 가지 기본 구조를 사용하여 모든 데이터 구조를 구성할 수 있으며 HashMap도 예외는 아닙니다. HashMap은 실제로 배열과 연결 목록의 조합인 "연결 목록 해시" 데이터 구조입니다.
위 그림에서 볼 수 있듯이 HashMap의 맨 아래 레이어는 배열 구조이고 배열의 각 항목은 연결 목록입니다. 새로운 HashMap이 생성되면 배열이 초기화됩니다.

/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */  transient Entry[] table;  

static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    Entry<K,V> next;  
    final int hash;  
    ……  
}

3. HashMap 액세스 구현:
1) 저장공간:

public V put(K key, V value) {  
    // HashMap允许存放null键和null值。  
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  
    if (key == null)  
        return putForNullKey(value);  
    // 根据key的keyCode重新计算hash值。  
    int hash = hash(key.hashCode());  
    // 搜索指定hash值在对应table中的索引。  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            return oldValue;  
        }  
    }  
    // 如果i索引处的Entry为null，表明此处还没有Entry。  
    modCount++;  
    // 将key、value添加到i索引处。  
    addEntry(hash, key, value, i);  
    return null;  
}

위의 소스코드에서 볼 수 있듯이 HashMap에 요소를 넣을 때 먼저 키의 hashCode를 기반으로 해시 값을 다시 계산하고 요소를 가져옵니다. 해시 값을 기반으로 배열의 위치(즉, 아래 첨자) 배열의 이 위치에 저장된 다른 요소가 있으면 이 위치의 요소가 새로 추가된 요소로 저장됩니다. 체인의 헤드에 배치되고 처음 추가된 요소는 체인의 헤드에 배치됩니다. 배열의 해당 위치에 요소가 없으면 요소는 배열의 해당 위치에 직접 배치됩니다.
addEntry(hash, key, value, i) 메소드는 계산된 해시 값을 기반으로 배열 테이블의 i 인덱스에 키-값 쌍을 배치합니다. addEntry는 HashMap에서 제공하는 패키지 접근 방식입니다.

void addEntry(int hash, K key, V value, int bucketIndex) {  
    // 获取指定 bucketIndex 索引处的 Entry   
    Entry<K,V> e = table[bucketIndex];  
    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
    // 如果 Map 中的 key-value 对的数量超过了极限  
    if (size++ >= threshold)  
    // 把 table 对象的长度扩充到原来的2倍。  
        resize(2 * table.length);  
}

시스템이 HashMap에 키-값 쌍을 저장하기로 결정하면 Entry에 있는 값을 전혀 고려하지 않습니다. 그러나 각 항목의 저장 위치를 계산하고 결정합니다. 시스템이 키의 저장 위치를 결정한 후에는 맵 컬렉션의 값을 키에 대한 액세서리로 완전히 간주할 수 있습니다.

hash(int h) 메서드는 키의 hashCode를 기반으로 해시를 다시 계산합니다. 이 알고리즘은 낮은 비트는 변경되지 않고 높은 비트는 변경될 때 발생하는 해시 충돌을 방지하기 위해 높은 비트 계산을 추가합니다.

static int hash(int h) {  
    h ^= (h >>> 20) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
}

HashMap에서 요소를 찾으려면 키의 해시 값을 기반으로 해당 배열에서 위치를 찾아야 함을 알 수 있습니다. 이 위치를 계산하는 방법은 해시 알고리즘입니다. 앞에서 언급했듯이 HashMap의 데이터 구조는 배열과 연결 목록의 조합이므로 당연히 이 HashMap의 요소 위치가 최대한 균등하게 분산되어 각 위치에 하나의 요소만 있기를 바랍니다. 해시 알고리즘을 사용하여 이 위치에서 연결 리스트를 순회하지 않고도 해당 위치의 요소가 우리가 원하는 요소인지 즉시 알 수 있으므로 쿼리 효율성이 크게 최적화됩니다.

특정 객체에 대해 hashCode() 반환 값이 동일한 한 hash(int h) 메서드를 호출하는 프로그램에서 계산한 해시 코드 값은 항상 동일합니다. 우리가 가장 먼저 생각하는 것은 해시 값을 배열 길이의 모듈로 취하여 요소의 분포가 상대적으로 균일하도록 하는 것입니다. 그러나 "모듈로" 연산의 소비는 여전히 상대적으로 큽니다. 이는 HashMap에서 수행됩니다. indexFor(int h, int length) 메소드를 호출하여 객체를 저장해야 하는 테이블 배열의 인덱스를 계산합니다. indexFor(int h, int length) 메소드의 코드는 다음과 같습니다:

static int indexFor(int h, int length) {  
    return h & (length-1);  
}

이 메소드는 h & (table.length -1)를 사용하여 저장 비트를 가져옵니다. 객체 및 HashMap의 기본 배열 길이는 항상 HashMap의 속도 최적화인 2의 n승입니다. HashMap 생성자에는 다음 코드가 있습니다.

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;

이 코드는 초기화 중 HashMap의 용량이 항상 2의 n승이 되도록 보장합니다. 즉, 기본 배열의 길이는 항상 2입니다. n승.
길이가 항상 2의 n제곱인 경우 h&(길이-1) 연산은 길이의 계수, 즉 h%length를 취하는 것과 동일하지만 &가 %보다 더 효율적입니다.
배열의 길이가 2의 n승일 때, 서로 다른 키에 대해 동일한 인덱스를 계산할 확률은 작습니다. 그러면 데이터가 배열에 고르게 분포되므로 충돌 가능성이 작습니다. 이에 비해 질의는 특정 위치에서 연결리스트를 순회할 필요가 없으므로 질의 효율이 더 높다.

위 put 메소드의 소스 코드에서 볼 수 있듯이 프로그램이 키-값 쌍을 HashMap에 넣으려고 하면 프로그램은 먼저 hashCode를 기반으로 Entry의 저장 공간을 결정합니다. () 키의 반환 값. 위치: 두 Entry 키의 hashCode() 반환 값이 동일하면 저장 위치도 동일합니다. 이 두 항목의 키가 같음 비교를 통해 true를 반환하는 경우 새로 추가된 항목의 값은 컬렉션의 원래 항목 값을 덮어쓰지만 키는 덮어쓰지 않습니다. 이 두 항목의 키가 같음 비교를 통해 false를 반환하는 경우 새로 추가된 항목은 컬렉션의 원래 항목과 함께 항목 체인을 형성하고 새로 추가된 항목은 항목 체인의 선두에 위치합니다. 설명을 계속 확인하세요. 특정 지침에 대한 addEntry() 메소드.
(2)

읽기

public V get(Object key) {  
    if (key == null)  
        return getForNullKey();  
    int hash = hash(key.hashCode());  
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  
        e != null;  
        e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
            return e.value;  
    }  
    return null;  
}

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。
4. HashMap的resize（rehash）：
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
5. HashMap的性能参数：
HashMap 包含如下几个构造器：
HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。
initialCapacity：HashMap的最大容量，即为底层数组的长度。
loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。
负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：

if (size++ >= threshold)     
    resize(2 * table.length);

6. Fail-Fast机制：
我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {  
    expectedModCount = modCount;  
    if (size > 0) { // advance to first entry  
    Entry[] t = table;  
    while (index < t.length && (next = t[index++]) == null)  
        ;  
    }  
}

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：
注意到modCount声明为volatile，保证线程之间修改的可见性。

final Entry<K,V> nextEntry() {     
    if (modCount != expectedModCount)     
        throw new ConcurrentModificationException();

在HashMap的API中指出：

모든 HashMap 클래스의 "컬렉션 뷰 메서드"에서 반환되는 반복자는 실패하지 않습니다. 반복자가 생성된 후 맵이 구조적으로 수정된 경우 반복자 자체의 제거 메서드를 통과하지 않는 한 다른 어떤 식으로든 수정될 때마다 반복자는 ConcurrentModificationException을 발생시킵니다. 따라서 동시 수정이 발생하는 경우 반복자는 향후 결정되지 않은 시간에 임의의 비결정적 동작을 위험에 빠뜨리지 않고 신속하게 완전히 실패합니다.

반복자의 빠른 실패 동작은 보장되지 않으며 일반적으로 비동기식 동시 수정이 있을 때 확실한 보장을 하는 것은 불가능합니다. 빠른 실패 반복자는 최선을 다해 ConcurrentModificationException을 발생시킵니다. 따라서 이 예외에 의존하는 프로그램을 작성하는 것은 실수입니다. 올바른 접근 방식은 반복자의 빠른 실패 동작을 프로그램 오류를 감지하는 데에만 사용해야 한다는 것입니다.

Java에서 HashMap의 구현 원리 분석

관련 기사