Java 수집 프레임워크 HashSet 및 HashMap 소스코드 상세 분석(그림)

전체 소개

HashSet과 HashMap을 함께 설명하는 이유는 Java에서 구현이 동일하고 전자는 후자에 불과하기 때문입니다. 패키징 계층입니다. 즉, HashSet에 HashMap(어댑터 모드) 이 있습니다. 따라서 이번 글에서는 HashMap을 분석하는 데 중점을 두겠습니다.

HashMap은 Map 인터페이스를 구현하여 null 요소를 배치할 수 있습니다. 이 클래스가 동기화를 구현하지 않는다는 점을 제외하면 나머지는 및 HashtableTreeMap과 달리 이 컨테이너는 요소의 순서를 보장하지 않습니다. 컨테이너는 필요에 따라 요소를 다시 해시할 수 있으며 요소의 순서도 다시 섞이므로 동일한 HashMap은 다른 시간에 반복됩니다. 순서는 다를 수 있습니다.

충돌을 처리하는 방법에 따라 해시 테이블을 구현하는 방법에는 두 가지가 있는데, 하나는 개방형 주소 지정 방식(Open addressing)이고, 다른 하나는 충돌 연결 리스트 방식(링크된 별도의 연결

목록). Java HashMap은 충돌 연결 목록 방법을 사용합니다.

위 그림에서 적절한 해싱

함수 를 선택하면 및 put() 메서드를 사용할 수 있음을 쉽게 알 수 있습니다. 일정한 시간 안에 완료됩니다. 그러나 get()HashMap을 반복할 때는 전체 테이블과 그에 따른 충돌 연결 목록을 순회해야 합니다. 따라서 반복이 빈번한 시나리오에서는 HashMap의 초기 크기를 너무 크게 설정하는 것은 적절하지 않습니다.

에는

HashMap의 성능에 영향을 미칠 수 있는 두 가지 매개변수인 초기 용량과 부하율이 있습니다. 초기 용량은 의 초기 크기를 지정하고 부하율은 자동 확장에 대한 임계 값을 지정하는 데 사용됩니다. table 개수가 entry개를 초과하면 컨테이너가 자동으로 확장되고 다시 해시됩니다. 많은 수의 요소가 삽입되는 시나리오의 경우 초기 용량을 더 크게 설정하면 재해시 횟수를 줄일 수 있습니다. capacity*load_factor

이

HashMap 또는 HashSet에 배치될 때 특별한 주의가 필요한 두 가지 방법이 있습니다: 및 hashCode(). equals() 메소드는 hashCode() 객체 가 어느 에 배치될지 결정합니다. 여러 객체의 해시 값이 충돌하는 경우 bucket 메소드는 이러한 객체가 "동일한지 여부를 결정합니다." 하나". 개체”equals(). 따라서 이나 HashMap에 커스텀 객체를 넣으려면 @Override HashSet, hashCode() 메소드가 필요합니다. equals()

메서드 분석

get()

get(<p>객체<code>get(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> <a href="http://www.php.cn/wiki/1051.html" target="_blank">key</a>) keykey)

메소드는 지정된 value 값에 따라 해당 getEntry(Object key)을 반환합니다. 이 메소드는 entry을 호출하여 해당 entry.getValue()을 가져옵니다. . 그런 다음 getEntry()을 반환하세요. 그러므로 가 알고리즘의 핵심이다.

hash() 알고리즘의 아이디어는 먼저 bucket 함수를 통해 key.equals(k)에 해당하는 첨자를 얻은 다음 충돌 연결 목록을 차례로 순회하고 entry 메서드를 사용하여 충돌 여부를 확인하는 것입니다. 당신이 찾고 있는

이 바로 그것입니다.

hash(k)&(table.length-1)위 그림에서 hash(k)%table.length는 과 동일합니다. 그 이유는 HashMaptable.length에서 table.length-1이 지수여야 하기 때문입니다. 2이므로 hash(k)즉, 이진 시스템의 하위 비트는 모두 1입니다.

을 사용한 AND는 해시 값의 상위 비트를 모두 지우고 나머지는 나머지입니다.

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表
         e != null; e = e.next) {//依次遍历冲突链表中的每个entry
        Object k;
        //依据equals()方法判断是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

put()

put(K key, V value)key, value 메소드는 지정된 map 쌍을 map에 추가합니다. 이 메소드는 먼저 getEntry()를 검색하여 튜플이 포함되어 있으면 직접 반환합니다. 검색 프로세스는 addEntry(int hash, K key, V value, int bucketIndex) 메소드와 유사합니다. entry 방식으로 삽입하면 🎜> 삽입 방식은 헤드 삽입 방식입니다.

//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//自动扩容，并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);//hash%table.length
    }
    //在冲突链表头部插入新的entry
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

remove()

remove(Object key)는 key 값에 해당하는 entry을 삭제하는 데 사용됩니다. 에 있습니다. removeEntryForKey(Object key) 메서드는 먼저 removeEntryForKey() 값에 해당하는 key을 찾은 다음 entry를 삭제합니다(연결된 목록의 해당 포인터 수정). 검색 과정은 entry 과정과 유사합니다. getEntry()

//removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);//hash&(table.length-1)
    Entry<K,V> prev = table[i];//得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {//遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
            modCount++; size--;
            if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
            else prev.next = next;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

HashSet

前面已经说过HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。这里不再赘述。

//HashSet是对HashMap的简单包装
public class HashSet<E>
{
    ......
    private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

위 내용은 Java 수집 프레임워크 HashSet 및 HashMap 소스코드 상세 분석(그림)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!