자바 기초 - 소스 분석 - hash 방법

자바 엔지니어 지식 트 리 / 자바 기초
Hash 집합 클래스 별 hash 방법 분석
Map 구현 클래스 에서 어떤 요 소 를 찾 으 려 면 key 의 hash 값 에 따라 대응 하 는 배열 의 위 치 를 구 해 야 합 니 다.이 위 치 를 어떻게 계산 하 느 냐 가 바로 hash 알고리즘 입 니 다.예 를 들 어 HashMap 의 데이터 구 조 는 배열 과 링크 의 결합 이다. HashMap 안의 요소 위 치 는 최대한 고 르 게 분포 하고 모든 위치 에 있 는 요소 의 수량 이 하나 밖 에 없 도록 해 야 한다. 그러면 hash 알고리즘 으로 이 위 치 를 구 할 때 해당 위치 에 대한 요 소 를 알 수 있 고 링크 를 옮 겨 다 니 지 않 아 도 된다.요약 하면 HashMap 은 JDK 1.7 과 1.8, HashTable 은 JDK 1.8, Concurrent HashMap 은 JDK 1.8 의 hash 알고리즘 에 관심 이 있 으 면 해당 유형 에서 왜 해당 하 는 hash 알고리즘 을 사용 하 는 지 연구 할 수 있다.
HashMap-JDK1.7

//HashMap-JDK1.7   Key  Entry
Node[] table;//      Node  ，   2  

// 1.  key hashCode    hash 。  
int hash = hash(key.hashCode());  
// 2.    hash    table    。  
int i = indexFor(hash, table.length); 
// 3.      Entry  
Entry e = table[i]
-------------------    ------------------------
//   key hashCode    hash 
static int hash(int h) {  
    h ^= (h >>> 20) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
} 
//     hash    table    
static int indexFor(int h, int length) {  
    return h & (length-1);  
} 

HashMap-JDK1.8

// HashMap-JDK1.8   Key  Entry
Node[] table;//      Node  ，   2  
// 1.  key hashCode    hash 。 
int hash = hash(key.hashCode());  
// 2.    hash    table    。  
int i = hash & (table.length-1);
// 3.      Entry  
Entry e = table[i]

-------------------    ------------------------    
//   key hashCode    hash 。  
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashTable-JDK1.8

// HashTable-JDK1.8   Key  Entry
private transient Entry,?>[] table;//      Entry  ，   2  
    
Entry,?> tab[] = table;
// 1.  key HashCode 。 
int hash = key.hashCode();
// 2.    hash    table    
int index = (hash & 0x7FFFFFFF) % tab.length;
// 3.      Entry  
Entry e = (Entry)tab[index];

ConcurrentHashMap-JDK1.8

// ConcurrentHashMap-JDK1.8   Key  Entry
transient volatile Node[] table;//      Node  ，   2  
// 1.  key hashCode    hash 。 
int hash = spread(key.hashCode());
// 2.    hash    table    。  
int i = hash & (table.length-1);
// 3.      Node  
Node e = tabAt(tab, i);


-------------------    ------------------------
//  key hashCode    hash 
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
//       tab    i     
static final  Node tabAt(Node[] tab, int i) {
    return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}