집 > 기사 > Java > Java 개선 장(33)------맵 요약

Java 개선 장(33)------맵 요약

黄舟원래의: 2017-02-11 10:24:081418검색

앞서 LZ는 HashMap, HashTable, TreeMap의 구현 방법을 자세히 소개하면서 데이터 구조, 구현 원리, 소스 코드 분석이라는 세 가지 측면을 자세히 설명했습니다. 아래 LZ는 Map에 대한 간략한 요약을 제공합니다.

2. 내부 해싱: 해시 매핑 기술

거의 모든 일반 지도는 해시 매핑 기술을 사용합니다. 우리 프로그래머들은 그것을 이해해야 합니다.

해시 매핑 기술은 요소를 배열로 매핑하는 매우 간단한 기술입니다. 해시 맵은 배열 결과를 사용하므로 임의의 키로 배열에 대한 액세스를 결정하기 위한 인덱싱 메커니즘이 있어야 합니다. 이 메커니즘은 배열 크기보다 작은 정수를 제공할 수 있습니다. 이 메커니즘을 해시 함수라고 부릅니다. Java에서는 그러한 정수를 찾는 것에 대해 걱정할 필요가 없습니다. 모든 객체에는 정수 값을 반환하는 hashCode 메서드가 있어야 하고, 우리가 해야 할 일은 정수로 변환한 다음 그 값을 배열로 나누는 것뿐입니다. 크기에서 나머지를 가져옵니다.

int hashValue = Maths.abs(obj.hashCode()) % size;

다음은 HashMap과 HashTable입니다.

----------HashMap------------
//计算hash值
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//计算key的索引位置
static int indexFor(int h, int length) {
        return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length;     //确认该key的索引位置

위치의 인덱스는 배열 내 노드의 위치를 나타냅니다. 다음 그림은 해시 매핑의 기본 원리 다이어그램입니다.

이 그림에서 1~4단계는 해당 요소를 찾는 것입니다. 배열 위치, 5~8단계는 요소를 배열에 삽입하는 것입니다. 삽입 과정에서 약간의 좌절감이 있을 것입니다. 동일한 해시 값을 가진 여러 요소가 있을 수 있으므로 동일한 인덱스 위치를 갖게 됩니다. 이는 여러 요소가 동일한 위치에 매핑된다는 의미입니다. 이 프로세스를 "충돌"이라고 합니다. 충돌을 해결하는 방법은 인덱스 위치에 연결 목록을 삽입하고 이 연결 목록에 요소를 추가하는 것입니다. 물론, 단순한 삽입은 아니고, HashMap의 처리 과정은 다음과 같습니다: 연결된 리스트가 null이면 해당 요소를 직접 삽입합니다. 키와 동일합니다. 존재하는 경우 원래 키의 값을 덮어쓰고 이전 값을 반환합니다. 그렇지 않으면 요소가 체인의 선두에 저장됩니다(저장된 첫 번째 요소는 체인의 끝에 배치됩니다). . 다음은 HashMap의 put 메소드로, 인덱스 위치를 계산하여 해당 요소를 적절한 위치에 삽입하는 전체 과정을 자세히 보여줍니다.

public V put(K key, V value) {
        //当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
        if (key == null)
            return putForNullKey(value);
        //计算key的hash值
        int hash = hash(key.hashCode());                 
        //计算key hash 值在 table 数组中的位置
        int i = indexFor(hash, table.length);            
        //从i出开始迭代 e,判断是否存在相同的key
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            //判断该条链上是否有hash值相同的(key相同)
            //若存在相同，则直接覆盖value，返回旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;    //旧值 = 新值
                e.value = value;
                e.recordAccess(this);
                return oldValue;     //返回旧值
            }
        }
        //修改次数增加1
        modCount++;
        //将key、value添加至i位置处
        addEntry(hash, key, value, i);
        return null;
    }

HashMap의 put 메소드는 해시 매핑의 기본 개념을 보여줍니다. 사실 다른 맵을 보면 원리가 비슷하다는 것을 알 수 있습니다!

3. 지도 최적화

크기는 1에 불과하며 모든 요소는 이 위치(0)에 매핑됩니다. ), 따라서 더 긴 연결 목록을 형성합니다. 업데이트하고 접근할 때 이 연결된 목록에 대해 선형 검색을 수행해야 하므로 필연적으로 효율성이 떨어집니다. 매우 큰 배열이 있고 연결된 목록의 각 위치에 하나의 요소만 있는 경우 액세스할 때 인덱스 값을 계산하여 객체를 얻을 것이라고 가정합니다. 이렇게 하면 검색 효율성이 향상되지만 낭비가 됩니다. 제어. 물론 이 두 가지 방법은 극단적이지만 최적화 아이디어를 제공합니다. 요소가 고르게 분산될 수 있도록 더 큰 배열을 사용합니다. 맵에는 효율성에 영향을 미치는 두 가지 요소가 있습니다. 하나는 컨테이너의 초기 크기이고 다른 하나는 로드 요소입니다.

3.1 구현 크기 조정

"버킷"으로서 사용 가능한 버킷 수(즉, 크기 내부 배열의)을 용량이라고 합니다. Map 개체가 여러 요소를 효과적으로 처리할 수 있도록 Map 자체 크기를 조정할 수 있도록 설계했습니다. 맵의 요소가 특정 양에 도달하면 컨테이너 자체의 크기가 조정되지만 이 크기 조정 프로세스에는 비용이 매우 많이 듭니다. 크기를 조정하려면 원래 요소를 모두 새 배열에 삽입해야 합니다. 우리는 인덱스 = hash(key) % 길이를 알고 있습니다. 이로 인해 원래 충돌하는 키가 더 이상 충돌하지 않고 충돌하지 않는 키가 이제 충돌하게 됩니다. 재계산, 조정 및 삽입 프로세스는 비용이 많이 들고 비효율적입니다. 따라서 지도의 예상 크기를 알기 시작하고 지도의 크기를 충분히 크게 조정하면 크기 조정의 필요성을 크게 줄이거나 아예 없앨 수 있어 속도가 향상될 가능성이 높습니다. 다음은 HashMap이 컨테이너 크기를 조정하는 과정입니다. 다음 코드를 통해 확장 과정의 복잡성을 확인할 수 있습니다.

void resize(int newCapacity) {
            Entry[] oldTable = table;    //原始容器
            int oldCapacity = oldTable.length;    //原始容器大小
            if (oldCapacity == MAXIMUM_CAPACITY) {     //是否超过最大值：1073741824
                threshold = Integer.MAX_VALUE;
                return;
            }

            //新的数组：大小为 oldCapacity * 2
            Entry[] newTable = new Entry[newCapacity];    
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
           /*
            * 重新计算阀值 =  newCapacity * loadFactor >  MAXIMUM_CAPACITY + 1 ? 
            *                         newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
            */
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);   
        }
        
        //将元素插入到新数组中
        void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

3.2、负载因子

为了确认何时需要调整Map容器，Map使用了一个额外的参数并且粗略计算存储容器的密度。在Map调整大小之前，使用”负载因子”来指示Map将会承担的“负载量”，也就是它的负载程度，当容器中元素的数量达到了这个“负载量”，则Map将会进行扩容操作。负载因子、容量、Map大小之间的关系如下：负载因子 * 容量 > map大小 ----->调整Map大小。

例如：如果负载因子大小为0.75（HashMap的默认值），默认容量为11，则 11 * 0.75 = 8.25 = 8，所以当我们容器中插入第八个元素的时候，Map就会调整大小。

负载因子本身就是在控件和时间之间的折衷。当我使用较小的负载因子时，虽然降低了冲突的可能性，使得单个链表的长度减小了，加快了访问和更新的速度，但是它占用了更多的控件，使得数组中的大部分控件没有得到利用，元素分布比较稀疏，同时由于Map频繁的调整大小，可能会降低性能。但是如果负载因子过大，会使得元素分布比较紧凑，导致产生冲突的可能性加大，从而访问、更新速度较慢。所以我们一般推荐不更改负载因子的值，采用默认值0.75.

Java 개선 장(33)------맵 요약

2. 내부 해싱: 해시 매핑 기술

3. 지도 최적화

3.1 구현 크기 조정

3.2、负载因子

最后

관련 기사