JAVA 용기 에 대한 HashMap

HashMap 의 데이터 구 조 를 연구 하 는 데 시간 이 좀 걸 렸 습 니 다.소스 코드 를 보고 디자이너 에 게 놀 랄 수 밖 에 없 었 습 니 다!
다음은 재 미 있 는 부분 을 말씀 드 리 겠 습 니 다.
1. key = null 에 대하 여.null 을 key 로 하면 액세스 속도 가 가장 빠르다 고 생각 합 니 다!put 와 get 전에 key 가 null 인지 아 닌 지 를 판단 하기 때문에 null 이면 key 가 null 인 값 을 직접 가 져 옵 니 다. 또한 key = null 이면 용기 Entry 배열 에 저 장 된 0 아래 표 시 를 직접 꺼 낼 수 있 습 니 다. 대상 이 Entry 배열 에 저 장 된 아래 표 시 는 하나의 hash 값 과 숫자의 길이 에 따라 줄 여 얻 은 것 입 니 다. key 가 null 이 라면 배열 아래 표 시 는 0 일 것 입 니 다.제때에 HashMap 자신 이 길이 조정 을 하고 다시 저장 할 때 도 마찬가지 입 니 다!빨리 기억 하 는 이 유 는 아래 가 0 이 라 서가 아니 라 put 와 get 전에 판단 하기 때 문 입 니 다!그러나 극단 적 인 상황 은 Entry [0] 라 는 체인 이 매우 길 고 속도 도 그리 빠 르 지 않다 는 것 이다.
 
2. HashMap 용량 변화.HashMap 용량 이 '부족' 할 때 용량 이 자동 으로 증가 합 니 다. 용량 을 늘 리 는 방식 은 지난번 배열 의 길이 * 2 입 니 다. HashMap 용량 을 수 동 으로 설정 하지 않 으 면 초기 값 은 16 이 고 loadfactor (기본 초기 값 은 0.75f) 가 현재 용량 증 가 를 진행 하 는 지 여 부 를 결정 합 니 다. 16 을 다 써 서 증가 하 는 것 이 아니 라 용량 > = loadfactor * 16 일 때 증가 합 니 다.이 인자 가 왜 0.75f 인지 에 대해 서 는 실천 에서 나 온 결론 일 수 있 습 니 다. 모든 기본 HashMap 은 12 개의 대상 을 넣 은 후에 다음 에 대상 을 놓 으 면 용량 크기 를 32 로 다시 바 꾸 고 다음 에 확장 여 부 를 판단 할 때 32 * loadfactor 로 결정 합 니 다.
 
3. put 일반 key, 일반 대상 의 과정.키 를 저장 합 니 다! =null 의 경우 대상 의 저장 과정 은 어 떻 습 니까?우 리 는 자주 String 을 key 로 사용 합 니 다. 식별 하기 편리 하기 위해 서 입 니 다. 사실은 key 도 일반적인 Object 대상 이거 나 자신 이 초기 화 한 대상 일 수도 있 습 니 다. 심지어 * class 일 수도 있 습 니 다. jvm 에서 볼 때 이것 은 여전히 Object 일 뿐 입 니 다. Object 라면 hashcode 가 있 습 니 다. 만약 에 hashcode 방법 을 복사 하지 않 았 다 면,자신 이 실현 한 대상 hashcode 는 jvm 대상 이 메모리 에 있 는 색인 값 을 직접 되 돌려 줍 니 다. 이것 이 바로 hashcode 자체 에 존재 하 는 의미 - 대상 의 빠 른 주소 지정 입 니 다.
    됐어, 멀 지 않 아!계속 put 하 는 과정,
먼저 HashMap 에 저 장 된 원자 Entry 를 소개 합 니 다. 그 는 Map 인터페이스 안의 내부 인터페이스 입 니 다. HashMap 은 이 를 실 현 했 고 네 가지 속성 이 있 습 니 다. Key, value, next, hash 입 니 다.key 는 우리 가 사용 하 는 키 입 니 다. value 는 저 장 된 대상 입 니 다.next 는 사실 Entry 대상 이기 도 합 니 다. 이것 은 체인 구조 라 고 생각 할 수 있 습 니 다. 그 는 다음 Entry 대상 을 가리 키 고 Entry 의 구체 적 인 대상 에 긴 체인 구 조 를 저장 할 수 있 습 니 다. 마지막 끝의 대상 인 next 는 null 입 니 다.hash 라 는 것 은 Entry 배열 의 아래 표 시 를 계산 하 는 근거 로 잠시 생각 합 니 다.너 도 간단 한 색인 이 라 고 생각 할 수 있다.
HashMap 은 put 대상 전에 hash 를 먼저 얻 습 니 다. 이 hash 는 나중에 Entry 배열 의 아래 표 시 를 하 는 근거 중 하나 입 니 다. 사실은 다른 근 거 는 배열 의 길이 입 니 다!나중에 얘 기해.
    hash 를 얻 는 과정 은 매우 복잡 합 니 다. 코드 를 보 세 요.
 

int hash = hash(key.hashCode());
...
// 
static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 먼저 key 의 hashcode 에 간 다음 에 징 그 러 운 부호 없 는 자리 이동 과 연산 을 했 습 니 다. 왜 자 리 를 옮 기 는 것 이 20, 12, 7, 4 인지 에 대해 의문 입 니 다. 마치 String 의 hashcode 가 왜 31 (제 블 로그 에서 토론 이 있 습 니 다) 인지........................................................
자, 여기 hash 라 는 값 을 계산 해 냈 습 니 다!HashMap 에 대상 을 저장 하기 전에 밑 에 배열 이 있 기 때문에 그 는 먼저 어떤 배열 아래 에 존재 해 야 하 는 지 계산 해 야 합 니까?그래서 다음 과 같은 계산 이 생 겼 다.

int i = indexFor(hash, table.length);
...//  
//      
static int indexFor(int h, int length) {
        return h & (length-1);
    }

 왜 length - 1 이 냐 는 질문 이 있 을 수 있 습 니 다. 사실은 간단 합 니 다. 배열 이 경 계 를 넘 지 않 기 위해 서 는 결과 가 커지 면 length - 1 밖 에 안 됩 니 다.
자, 저장 할 배열 아래 표시 도 계산 되 었 습 니 다. 이제 대상 에 넣 어야 합 니 다.....................................................

 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
           //        e.hash==hash ？     
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               //     
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

 코드 를 보면 대상 을 넣 은 후에 바로 위 치 를 정 하 는 table [i] 를 볼 수 있 습 니 다. 안에 있 는 i 는 바로 이전 index For 에서 나 온 값 입 니 다.이 Entry 체인 으로 직접 와 서 나무 와 같은 key 를 비교 합 니 다. 주석 에 'e. hash = = hash' 라 고 쓰 여 있 는 것 은 검색 속 도 를 높이 기 위해 서 입 니 다.(우 리 는 항상 hashcode 와 equals 방법 을 덮어 씁 니 다. hashcode 가 같 지 않 으 면 바로 같은 대상 이 아니 라 고 판결 할 수 있 습 니 다. hashcode 가 같 으 면 equals 대 비 를 합 니 다. 일반적인 Object 를 덮어 쓰 는 equals 방법 이 없 는 대상 은 메모리 주소 가 같 는 지 비교 하 는 것 입 니 다)"직접 숫자의 대 비 는 key 의 대비 보다 빠 릅 니 다. hash 값 이 같 지 않 은 것 을 발견 하면 바로 다음 순환 대 비 를 실행 할 수 있 습 니 다. 찾 으 면 새로운 오래된 값 으로 교체 합 니 다. 찾 지 못 하면 바로 Entry 대상 을 이 Entry 체인 에 추가 하고 다음 절 을 주의 하 십시오.

//   i         
// int hash = hash(key.hashCode());
//int i = indexFor(hash, table.length);
addEntry(hash, key, value, i);
.....
//
void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);//  
    }

 이렇게 한 대상 이 들 어 갑 니 다!
 
넷 째, get 방법 에 대하 여.

public V get(Object key) {
        if (key == null)
            return getForNullKey();//key null   
        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 을 도와 구체 적 으로 어떤 Entry 원 자 를 신속하게 찾 을 수 있 습 니 다. 현재 많은 회사 들 이 Mysql 을 사용 할 때 단일 표 데이터 의 양 이 너무 많아 서 조작 표 의 속도 가 느 려 지 는 해결 방법 은 바로 라 이브 러 리 분 표 입 니 다. 사실은 하나의 이치 입 니 다. 라 이브 러 리 분 표 도 이곳 의 Entry 원자 에 해당 합 니 다. hash 는 마치 하나의 Entry 원자 처럼 보 입 니 다.색인, 빨리 찾 아 주세요!
 
5. entry Set 방법 에 대하 여.
    맵 은 맵 을 옮 겨 다 니 는 데 편리 하도록 entry Set 방법 을 제공 하여 하나의 Set 의 하위 클래스 로 전환 시 켰 습 니 다. 각 하위 클래스 에서 스스로 옮 겨 다 니 는 방법 을 실현 합 니 다. HashMap 의 경우 Entry [0] 부터 옮 겨 다 니 며 Entry [0] 라 는 링크 를 옮 겨 다 니 고 나 서 Entry [1] 를 옮 겨 다 니 는 것 과 유사 합 니 다. 2 차원 배열 이나.. 깊이 옮 겨 다 니 는 것 과 유사 합 니 다!
    그 중 에 또 하나의 keyset 방법 도 entry set 방법 과 유사 하 며 내부 에서 만 key 를 entry 에서 분리 합 니 다.
 
마지막 으로 puutAll 방법 에 대해 서 는 puut 된 map 안의 내용 을 copy 또는 현재 map 에 덮어 쓰 고 그 전에 용량 계산 이나 확장 작업 을 하 며 마지막 으로 puut 방법 을 순환 적 으로 호출 합 니 다.
 
 
=======================================
 
자, 보 니 모두 자바 의 기반 이 었 습 니 다. 동생 은 이제... 고 개 를 돌려 이런 디자인 사상 을 보 는 것 도 재 미 있 었 습 니 다. 위 내용 은 개인 적 인 YY 가 많 았 습 니 다. 의견 이 다 르 면 아낌없이 가르쳐 주 셨 으 니 높 은 분 들 의 조언 을 바 랍 니 다.