왜 HashMap 안의 배열 size 가 2 의 차 멱 이 어야 하 는 지 아 세 요?

최근 에 간단 한 분리 자물쇠 종 류 를 쓰 고 있 습 니 다.
 
요구: 키 에 따라 hash 를 진행 하여 Lock 을 얻 고 잠 금 맵 에 대한 확률 차이 가 많 지 않 습 니 다.예 를 들 어 160 개의 Key 는 16 개의 자물쇠 에 분포 되 어 있 고 약 10 개의 Key 는 같은 자물쇠 에 투사 되 기 때문에 이렇게 해야만 병행 효율 이 높다.
 

public class SplitReentrantLock {

	private Lock[] locks;

	private int LOCK_NUM;

	public SplitReentrantLock(int lockNum) {
		super();
		LOCK_NUM = lockNum;
		locks = new Lock[LOCK_NUM];
		for (int i = 0; i < LOCK_NUM; i++) {
			locks[i] = new ReentrantLock();
		}
	}

	/**
	 *    ,   HashMap hash  
	 * 
	 * 
	 * @param key
	 * @return
	 */
	public Lock getLock(String key) {

		int lockIndex = index(key);
		return locks[lockIndex];
	}

	int index(String key) {
		int hash = hash(key.hashCode());		
		return hash & (LOCK_NUM - 1);
	}

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

 
 
사용법:
 

SplitReentrantLock locks = new SplitReentrantLock(16);
  Lock lock =locks.getLock(key); 
  lock.lock();
  try{
     //......
   }finally{
   lock.unlock(); 
   }

 
HashMap 의 hash 알고리즘 을 사용 하면 상기 요구 에 도달 할 수 있다 고 생각 했 는데 테스트 를 하 다가 깜짝 놀 랐 습 니 다.
 
테스트 코드:
 
 

public class SplitReenterLockTest extends TestCase {

	public void method(int lockNum, int testNum) {

		SplitReentrantLock splitLock = new SplitReentrantLock(lockNum);
		Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
		for (int i = 0; i < lockNum; i++) {
			map.put(i, 0);
		}
		for (int i = 0; i < testNum; i++) {
			Integer key = splitLock.index(RandomStringUtils.random(128));
			map.put(key, map.get(key) + 1);
		}

		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			System.out.println(entry.getKey() + " : " + entry.getValue());
		}
	}

	public void test1() {
		method(50, 1000);}
 
}

 
 
결과: 1000 개의 무 작위 키 의 hash 는 8 개의 Lock 에 만 비 치 는 것 이지 평균 50 개의 Lock 에 비 치 는 것 이 아니다.
그리고 0, 1, 16, 17, 32, 33, 48, 49 의 배열 아래 표 시 된 Lock 위 에 고정 적 으로 분포 되 어 있 습 니 다. 왜 일 까요?
 
하면, 만약, 만약...
 

public void test1() {
	method(32, 1000);
}

 
 결과: 1000 개의 무 작위 키 의 hash 가 32 개의 Lock 에 매 핑 되 었 고 기본적으로 평균 적 으로 분포 되 어 있 습 니 다.
 
문제: 왜 50 과 32 의 hash 의 효과 차이 가 그렇게 큽 니까?
 
다시 한 번 2, 4, 8, 16, 64, 128 을 테스트 해 보 니 기본적으로 모든 Lock 위 에 평균 적 으로 분포 되 어 있 는 것 으로 나 타 났 다.
 
평균 분 포 를 얻 은 이 수 들 은 모두 2 의 차 멱 인 데, 설마 hash 알고리즘 은 2 진법 과 관계 가 있 습 니까?
 
hash 알고리즘 보기:   
 

   int index(String key) {
		int hash = hash(key.hashCode());		
		return hash & (LOCK_NUM - 1);
	}

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

 먼저 신기 한 (ps: 왜 이렇게 연산 하 는 지 모 르 겠 지만 무식 한 나 는 신기 한 것 으로 만 형용 할 수 있다) 의 비트 연산 을 거 쳐 마지막 으로 LOCKNUM - 1 로 연산 을 진행 합 니 다.
 
이 게시 물의 관건 은 바로 이것 과 연산 에 있 습 니 다. 연산 후의 결과 가 평균 적 으로 분포 되 어 있 는 지 여 부 는 LOCK 에 있 습 니 다.NUM - 1 의 바 이 너 리 중 1 의 자릿수 는 몇 개 입 니까?모두 1 이 라면 0 에서 LOCK 까지 평균 분포 되 어 있 을 것 입 니 다.NUM - 1 위.그렇지 않 으 면 지 정 된 몇 자리 만 분포 한다.
 
다음은 50 과 32 로 설명 한다.
 
Key 가 hash 를 실행 하면 hash 값 을 h 로 얻 을 수 있 습 니 다.
예 를 들 어 내 가 테스트 한 데이터 중 일부 h 의 바 이 너 리 값:
 

1100000010000110110101010001001
10111100001001110111000100010001
11111011111010101010000111001001
11001010011000100110110111011111
10001010100010111101011010011110

 50 의 바 이 너 리 값: 110010. 1 을 뺀 바 이 너 리: 110001
 32 의 바 이 너 리 값: 100000. 1 을 뺀 바 이 너 리: 11111
 
따라서 h 와 49 (즉 110001) 와 의 결 과 는
000000  ： 0
000001  ： 1
010000  ： 16
010001  ： 17
100000  ： 32
100001  ： 33
110000  ： 48
110001  ： 49
 
그리고 (즉 11111) 과 의 결 과 는 다음 과 같다.
00000
00001
00010
....
11110
11111
 
이제 이 유 는 알 겠 지?LOCK_NUM - 1 2 진법 에서 1 인 자리 수가 많 을 수록 분포 가 평균 적 이다.
 
 
이것 이 바로 HashMap 의 기본 크기 가 2 의 차 멱 이 고 요 소 를 추가 할 때 일정한 수량 을 초과 하면 수량 을 원래 의 두 배로 늘 리 는 이유 입 니 다. 그 중에서 매우 중요 한 이 유 는 hash 의 평균 분 포 를 위 한 것 입 니 다.