[JAVA] HashMap 구현 - Hash 값으로 index 만들어서 검색 효율 높이기

직접 HashMap을 구현하는 작업중 의문이 발생했다.

 

 HashMap은 제너릭으로 Key값과 Value 값을 가진다.

그래서 처음에는 Key에 대한 ArrayList와 Value에 대한 ArrayList<> 를 만들어서 HashMap을 구현했다.

 

그런데 이렇게 하면 자료구조가 맞나..? 해시값을 사용하지도 않았을 뿐더러

검색 시간복잡도가 좋다고 알고있는 HashMap이 너무 구려진다. 

그래서 다시 해시값을 이용해서 다시 구현했다.

 

간단한 HashMap을 구현하는 것이기 때문에 Key 값은 따로 저장하지 않고 해시값을 구해서 index로만 사용했다.

 

---

 

[문제 발생]

그런데, Key의 해시값을 구하면 배열의 index로는 도저히 사용할 수 없는 정수값이 나온다. 그래서 배열의 크기로 해시값을 나눈 나머지를 index로 사용해서 문제를 해결했다.

그런데 예를 들어 배열의 사이즈가 10이라고 가정한다면, 해시값이 101이 나온 Key와 201이 나온 Key가 충돌이 발생한다고 생각이 들었다.

 

---

 

[문제 해결]

# 보조 해시 함수

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

기존에는 하위 a개의 비트만 사용하기 때문에 충돌이 발생할 가능성이 제법 있었다.

하지만 해당 코드는 상위비트값이 반영될 수 있도록 하는 코드이다.

 

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

    public int getHashIndex(K k){
        return hash(k) % capacity;
    }

이런식으로 Key값의 index를 충돌이 나지 않게 뽑아서 배열의 삽입과 삭제, 수정에 활용했다.

 

---

 

Q)해시 값을 위와 같이 나누게 되면 해시 충돌이 발생할 확률이 높아진다. 가 무슨 뜻인가요?

M이 16이라고 하면, 나머지는 0~15밖에 안되므로, 32비트의 해시가 나오게 해시 함수가 설정되어있어도, 0~15사이의 값이 계속나온다.