Java 컬렉션 클래스 Hashmap에 대한 자세한 소개(코드 예)-java지도 시간-php.cn

Java 컬렉션 클래스 Hashmap에 대한 자세한 소개(코드 예)

不言

풀어 주다： 2019-02-19 13:34:13

앞으로

2409명이 탐색했습니다.

이 기사는 Java 컬렉션 클래스 Hashmap에 대한 자세한 소개(코드 예제)를 제공합니다. 이는 특정 참조 가치가 있으므로 도움이 될 수 있습니다.

1. HashMap 소개

HashMap은 프로그래머의 개발 과정에서 매우 일반적으로 사용되는 컬렉션 클래스입니다.

해당 키 중 하나를 사용할 수 있습니다. 개발 존재와 교체의 특징은 업데이트된 중복 제거 작업을 실현합니다.

또 다른 편의상 map과 fastJson을 사용하여 필요한 json 데이터 형식을 빠르게 구성할 수 있습니다.

jdk1.8 이전에는 HashMap이 배열 + 연결리스트 형태로 존재했습니다. Put 키의 hashCode를 perturbation 함수로 계산하여 해시 값을 얻은 후 (n-1)&hash로 값을 계산했습니다. 해당 위치(n은 배열의 길이를 나타냄),

해시 충돌이 발생하면 먼저 키가 존재하는지 확인하고, 존재하면 덮어씁니다. 그렇지 않으면 충돌을 해결하고 양식을 작성합니다. 연결리스트.

그러나 jdk1.8 이후에는 HashMap이 변경되었습니다. 현재 연결 목록의 길이가 임계값(기본값은 8)보다 크면 연결 목록이 빨간색-검정 트리로 변환되어 검색 속도가 빨라집니다. .

II. HashMap 속성

//HashMap의 기본 초기 용량 2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << // 16

//최대값 HashMap 용량
static final int MAXIMUM_CAPACITY = 1 << 30;

//기본 로딩 요소는 배열 길이입니다
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//버킷의 노드 수가 이 값보다 크면 레드-블랙 트리로 변환됩니다
static final int TREEIFY_THRESHOLD = 8;

// 버킷의 노드 수가 이 값보다 작으면 트리는 연결 목록으로 변환됩니다.
static final int UNTREEIFY_THRESHOLD = 6;

// 버킷의 구조 레드-블랙 트리에 해당하는 테이블의 최소 크기로 변환
static final int MIN_TREEIFY_CAPACITY = 64;

// 요소를 저장하는 배열, 항상 2의 거듭제곱
temporary Node[] table;

/ / 특정 요소의 집합 저장
temporary Set>entrySet;

// 요소의 길이는 배열의 길이와 같지 않습니다.
temporary int size;

// 맵 구조의 확장 및 변경마다 카운터
temporary int modCount;

// Critical value 실제 크기(용량 * 채우기 비율)가 임계 값을 초과하면 용량이 확장됩니다( *whensize大于等于threshold的时候，并不一定会触发扩容机制，但是会很可能就触发扩容机制，只要有一个新建的Entry出现哈希冲突，则立刻resize )
int Threshold;

// Fill Factor Size>=threshold인 경우 배열의 확장을 고려해야 합니다. 즉, 배열을 확장해야 하는지 측정하는 기준을 의미합니다
final float loadFactor;

3. HashMap

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

로그인 후 복사

의 확장 메커니즘은 다음과 같습니다. tableSizeFor의 코드는 다음과 같습니다.

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

로그인 후 복사

>>> 왼쪽 및 오른쪽 숫자

이 방법은 전달된 초기화 용량을 2의 제곱의 거듭제곱인 숫자로 변환하므로 여기서 HashMap의 용량은 2의 제곱의 거듭제곱이어야 한다고 고정됩니다

2의 제곱의 거듭제곱인 이유는 다음과 같습니다.

1.put 메소드 소스 코드:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((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
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

로그인 후 복사

여기서 p = tab[i = (n - 1) & hash])를 참조하세요. == null 이 문장(n - 1) & 해시는 위치로 계산되며, 이 탭의 위치가 비어 있는 경우 직접 삽입 작업을 수행합니다.

예를 들어 16개의 직위가 있고 4명의 학생이 고유한 학생 번호

name	student number
Zhang San	1
이사	2
王五	3
老lee	4

此时我们分配位置的时候可以采用 1%16 = 1；2%16=2；3%16 = 3；4%16=4；给他们分配位置,但是考虑到性能问题。由于%操作比&慢10倍左右，因此采用&运算会提高性能。

通过限制length是一个2的幂数， (n - 1) & hash和hash%n结果是一致的。这就是为什么要限制容量必须是一个2的幂的原因。

比如2的hashCode是2 那么它对应的二进制是（0000 0010）

假设n=16

那么n-1=15对应的二进制是 1111 1111 & 0000 0010 = 1111 1111 = 0010 = 2

2%16=2

得到(n - 1) & hash和hash%n结果是一致的,考虑到性能所以每次的扩容都是以2的幂次方扩容。

四.HashMap的简单应用

public  static void mapMethod() {
		HashMap<String, Object> map = new HashMap<>();
		map.put("zhangsan", 11);
		map.put("lisi", 11);
		//重复key会覆盖
		map.put("zhangsan", 22);
		//便利
		for(String key:map.keySet()) {
			//根据key获取value
			System.out.println(key+"=======value:"+map.get(key));
		}
		//containsKey方法判断当前map是否包含该方法
		System.out.println(map.containsKey("zhangsan"));
		//size打印map的长度
		System.out.println(map.size());
		//移除key
		map.remove("zhangsan");
		//判断是否存在value
		System.out.println(map.containsValue("22"));
	}

로그인 후 복사