[TIL] 자료구조 - 재해싱

※ 재해싱

- 체인 해시에서 해시가 너무 많이 차는 경우 크기 조정을 해야 할 필요가 있다.

예를들어, 우선 크기가 2배인 배열을 만들고 다음 코드에 따라 data의 index를 다시 결정해 연결 리스트의 요소들을

옮긴다.

 

// data의 index 결정
int idx = x.hashCode(s);
idx = idx & ox7FFFFFFF;
idx = idx % tableSize;

 

연결 리스트의 위치를 그대로 하고 옮기면 정보를 다시 찾거나 제거하려 할 때 문제가 발생하는데 그 이유는 바로 정보의 위치를 지정할 때 다른 정보는 그대로이지만 tableSize만 바뀌기 때문이다. 그래서 각 요소의 위치를 초기화 한 뒤에 처음부터 다시 위치 지정을 해주어야 한다.