Hash란?
Hash란 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 갖는다.( ArrayList의 장점 )
그리고 데이터를 추가/삭제시 기존 데이터를 밀어내거나 당기는 작업이 없도록 (연결리스트의 장점) 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다
Hash에서 사용하는 내부적인 배열을 Hash Table이라고 하며 크기에 따라 성능차이가 있다.
Hash Table
Hash Table은 key-value에서 key를 테이블에 저장할 때 key값을 Hash Method를 이용해 계산을 수행한 후 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다.
Hash Method
위에서 설명했듯 Hash는 특별한 알고리즘을 이용한다고 하였는데 이 알고리즘을 구현한 메소드를 Hash Method라고 하며 Hash Method에 의해 반환된 데이터의 고유 숫자값을 Hash Code라고 한다.
Hash Method의 특성으로는
1. 동일한 입력값에 대해 동일한 출력값을 보장한다.
2. 출력 값은 가능한 고른 범위에 균일하게 분포된다.
자바에서는 Object클래스의 hashCode() 메소드를 이용하여 모든 객체의 HashCode를 쉽게 구할 수 있다.
하지만 입력값이 달라져도 드물게 동일한 출력값이 나오는 경우가 있는데 이런 경우를 해시충돌이라고 한다.
Hash 충돌
해시함수에서 출력된 해시코드값이 다른입력값과 동일할때 발생되는것을 해시충돌이라 하고 이러한 해시충돌은 특정 키의 버켓에 데이터가 집중된다는 것을 의미합니다. 그래서 너무 많은 해시 충돌은 해시테이블의 성능을 떨어뜨립니다.
해시충돌을 최소화 하기위해선 해시함수를 잘 정의하여 사용해야 한다. 하지만 해시함수의 입력값은 무한이지만 출력값은 유한하므로 해시충돌은 반드시 발생합니다.
이러한 해시충돌을 해결하기 위해 여러 방법이있다.
Hash충돌의 해결방법
1. 체이닝(Chaning)
버켓 내의 연결리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다.
Java8이상에서는 더 향상된 방법으로 충돌을 회피하는데, 충돌된 데이터가 8개가 모이면 연결리스트를 트리로 변형하고 해당 값이 6개에 이르면 다시 연결리스트로 변경시킨다. 8개에서 7개가 아닌 이유는 잦은 연결리스트와 트리로의 변경으로 인한 성능저하를 막기 위함이라 한다.
2. 개방 주소법(Open Addressing)
체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다. 하지만 개방 주소법의 경우에는 다르다. 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방주소법이라고 하며, 개방주소법은 대표적으로 3가지가 있다.
1. 선형탐색 : 해시 충돌시 다음 버켓, 혹은 몇개를 건너뛰어 데이터를 삽입한다.
2. 제곱 탐색 : 해시 충돌시 제곱만큼 건너뛴 버켓에 데이터를 삽입
3. 이중 해시 : 해시 충돌시 다른 해시함수를 한 번 더 적용한 결과를 이용함.Java에서는 체이닝기법으로 해시충돌을 회피하고있는데 그 이유는 개방주소법을 사용할 경우 데이터 삭제시 효율적인 처리가 어려워서 입니다.
