jdk 7 에서 HashMap 의 지식 포인트 요약

HashMap 의 몇 가지 중요 한 변수
기본 초기 용량 은 2 의 n 제곱 이 어야 합 니 다.

static final int DEFAULT_INITIAL_CAPACITY = 16;

최대 용량 은 구조 방법 을 통 해 들 어 오 는 용량 이 그것 보다 더 클 때 이 최대 용량 으로 2 의 n 제곱 이 어야 한다.

static final int MAXIMUM_CAPACITY = 1 << 30;

기본 부하 인자

static final float DEFAULT_LOAD_FACTOR = 0.75f;

키 쌍 을 저장 하 는 데 사용 합 니 다.키 쌍 은 모두 Entry 에 저 장 된 것 을 볼 수 있 습 니 다.

transient Entry<K,V>[] table;

//capacity * load factor,            
int threshold;

HashMap 의 요 소 는 table 이라는 Entry 배열 로 저 장 됩 니 다.기본 크기 는 16 입 니 다.
capacity:배열 의 용량

load_factor:부하 인자

4

threshold:실제 적재 할 수 있 는 용량 은 위의 두 개의 상승 과 같 고 size 가 threshold 보다 크 면 rehash 를 진행 합 니 다.

jdk 7 에 서 는 key 가 String 일 때 차별 대 우 를 했 습 니 다.alternative hashing 이 있 을 수 있 습 니 다.하지만 이것 은 jdk 8 에서 삭제 되 었 습 니 다.
기억 구조

Entry 는 key 와 value 뿐만 아니 라 다음 next 를 가리 킬 수 있 는 링크 구조 입 니 다.

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

 /**
  * Creates new entry.
  */
 Entry(int h, K k, V v, Entry<K,V> n) {
  value = v;
  next = n;
  key = k;
  hash = h;
 }
 ...

put 방법

public V put(K key, V value) {
 if (key == null)
  return putForNullKey(value);
 int hash = hash(key);
 int i = indexFor(hash, table.length);
 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;
  }
 }

 modCount++;
 addEntry(hash, key, value, i);
 return null;
 }

우선 hash 방법 을 통 해 hashcode 를 처리 합 니 다:

final int hash(Object k) {
 int h = 0;
 h ^= k.hashCode();

 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }

key 의 hashcode 값 에서 만 처 리 된 것 을 볼 수 있 습 니 다.hash 를 통 해 계 산 된 값 은 index For 방법 으로 있 을 table 아래 표 시 를 찾 을 수 있 습 니 다.

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

이 방법 은 사실 대 4 567914 에 해당 한다.
삽입 할 key 가 null 일 때 putForNullKey 방법 으로 처리 합 니 다.

 private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null) {
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
  }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
 }

puutForNullKey 방법 은table.length이 위치 에서 만 옮 겨 다 닙 니 다.key 는 null 이 고 table 의 첫 번 째 위치 에 만 놓 여 있 기 때문에 아래 는 0 으로 표시 되 어 있 습 니 다.옮 겨 다 니 면서 key 가 null 인 것 을 발견 하면 새 value 를 바 꾸 고 오래된 value 로 돌아 가 끝 납 니 다.만약 key 가 null 이 아니라면,addEntry 방법 으로 Entry 를 추가 합 니 다.

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 = indexFor(hash, table.length);
 }

 createEntry(hash, key, value, bucketIndex);
 }

jdk 7 에서 resize 의 조건 이 바 뀌 었 음 을 볼 수 있 습 니 다.4.567914.그리고 table 에 있 는 홈 에 Entry 가 있 을 때 만 resize 가 발생 합 니 다.즉,4.567914.하지만 홈 마다 적어도 하나의 Entry 가 있 을 때 까지 기 다 려 야 확대 할 수 있다.그리고 사이즈 조절 할 때마다 용량 이 배로 늘 어 납 니 다.

void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
 }

마지막 으로 createEntry 를 보 세 요.이 통 의 첫 번 째 Entry 를 저장 하고 새로운 Entry 를 만들어 첫 번 째 위치 에 두 고 원래 의 Entry 를 뒤에 연결 합 니 다.여기 서 사용 하 는 것 은 머리 삽입 법 으로 요 소 를 삽입 하 는 것 이다.
get 방법
사실 get 방법 과 put 방법 은 똑같다.

public V get(Object key) {
 if (key == null)
  return getForNullKey();
 Entry<K,V> entry = getEntry(key);

 return null == entry ? null : entry.getValue();
 }

key 가 null 일 때,가 져 가세 요table[0]가 져 가세 요:

private V getForNullKey() {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null)
  return e.value;
 }
 return null;
 }

그렇지 않 으 면 getEntry 방법 을 호출 합 니 다:

final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 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 != null && key.equals(k))))
  return e;
 }
 return null;
 }

이 방법 도 key 의 hashcode 를 통 해 아래 표 시 를 계산 하고 이 아래 표 시 된 Entry 체인 을 옮 겨 다 니 며 key 의 메모리 주소 가 같 거나 equals 가 같 으 면 찾 았 음 을 설명 합 니 다.
hash 의 원칙
A.등 멱 성.Hash 값 을 가 져 오 는 작업 을 몇 번 을 수행 하 든 대상 이 변 하지 않 는 다 면 Hash 값 은 고정 되 어 있 습 니 다.처음 가 져 오 는 것 이 N 번 가 져 오 는 것 과 다르다 면 사용 하기 가 매우 번거롭다.
B.대등 성.두 대상 equal 방법 이 true 로 되 돌아 오 면 hash 값 도 같 아야 합 니 다.예 를 들 어 obba 를 key 로 HashMap 에 저장 한 다음 new 는 obdb 를 만 들 었 습 니 다.당신 이 보기에 obj B 와 obj A 는 하나의 물건(그들 equal 때 문)이지 만,obj B 를 사용 하여 hashMap 에서 물건 을 꺼 낼 수 없습니다.
C.서로 이성.두 대상 equal 방법 이 false 로 되 돌아 가면 hash 값 이 같 을 수 있 지만 다른 것 이 좋 습 니 다.이것 은 필요 한 것 이 아니 라 이렇게 하면 hash 류 작업 의 성능(충돌 확률 이 낮 음)을 향상 시 킬 수 있 습 니 다.
hash 충돌 해결 방법:
개방 주소 법
체인 주소 법
hashmap 는 체인 주소 법 을 사용 합 니 다.이런 방법 은 퇴적 현상 이 없 지만 next 지침 은 추가 공간 을 차지 합 니 다.
jdk 8 의 HashMap 과 구별
jdk 8 에 서 는 size>=thresholdhash 값 을 계산 한 다음 에 이 hash 값 을 통 해 이 key 를 찾 습 니 다.그러나 충돌 이 발생 할 때 링크 와 빨 간 검 은 나무 두 가지 방법 으로 처리 합 니 다.노드 개수 가 적 을 때 링크(Node 로 저장)를 사용 하고 개수 가 많 을 때 빨 간 검 은 나무(TreeNode 로 저장)를 사용 하 며 노드 도 Entry 라 고 부 르 지 않 습 니 다.노드 와 트 리 노드 로 나 뉘 었 다.최 악의 경우 링크 가 찾 는 시간 복잡 도 는 O(n)이 고 빨 간 검 은 나 무 는 O(logn)이 므 로 HashMap 의 효율 을 높 일 수 있다.jdk 8 의 HashMap 에서 변 수 를 정의 합 니 다 TREEIFYTHRESHOLD,노드 개수 로>=TREEIFYTHRESHOLD-1 시,HashMap 은 붉 은 검 은 나무 로 저 장 됩 니 다.
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 면 댓 글 을 남 겨 주 십시오.