해시(Hash)란?

해시란 데이터를 다루는 기법으로 검색과 저장을 빠르게 하는 기법이다. 보통 리스트에 데이터를 저장하고 원하는 데이터를 찾는 방법으로 가장 기본적인 방법이 for나 while로 리스트의 데이터를 하나씩 순회하면서 확인하는 방법일 것이다. 하지만 리스트가 백만개정도의 데이터를 가지고 있고, 내가 원하는 데이터가 가장 마지막 백만번째 인덱스에 위치해 있다고 가정한다. 그럼 내가 원하는 데이터를 얻기 위해 백만개의 데이터를 모두 확인해야 하는 문제가 생길 수 있다. 만약 내가 원하는 데이터가 위치한 인덱스를 알고 있다면 바로 검색이 가능하긴 하다. 하지만 위치한 인덱스를 알지 못한다면 어떻게 할까? 이런 문제점을 해결하기 위한 방법이 해시다. 해시를 이용하면 중복되지 않는 key와 value(중복되어도 상관없음)가 한 쌍을 이루고, key값이 배열의 인덱스로 변환된다. 쉽게 말하면 인덱스 대신 key라는 중복되지 않는 값을 통해 원하는 데이터를 바로 검색하는 방식이다. 인덱스는 숫자이므로 사람의 입장에서 직관성이 떨어진다. 배열을 만들고 0번째 인덱스에는 어떤 데이터가 있고, 1번째 인덱스에는 어떤 데이터가 있고,... 이렇게 어떤 인덱스에 어떤 데이터가 들어가 있는지를 모두 외울 수는 없는 노릇이다. 하지만 인덱스가 직관성있게 이름이라면 어떨까? '이름'이라는 인덱스에는 이름 데이터가 있고, '나이' 인덱스에는 나이 데이터가 있고,... 이렇게 해시를 사용하면 이름 데이터가 필요하면 이름 인덱스를 호출하면 되므로 전보다 데이터 검색이 수월해진다.

해시함수란?

위에서 직관성을 위해 0,1,2 같은 숫자 인덱스를 사용하지 않고, "이름 인덱스"처럼 직관성있는 인덱스를 사용한다고 했다. 하지만 더 정확하게 말하자면 "이름 인덱스"도 사실 0,1,2 같은 숫자 인덱스다. 해시 기술을 이용한 해시함수가 "이름 인덱스"같은 문자열을 숫자형태로 바꿔주는 것이다. 이렇게 바뀐 값을 해시코드라고 하고 해시 테이블에 해당 값들을 저장해 관리한다. 즉, 우리는 "이름"으로 원하는 데이터를 호출할지라도 실제로는 해시함수가 "이름"을 해시코드로 바꾸어 해시테이블에 저장해놓아 이 해시테이블 속 해시코드를 검색하는 식으로 동작하는 것이다.

충돌( 해시함수를 통한 해시코드값들이 중복되면? )

해시함수로 바꾼 해시코드값들이 중복된다면 문제가 생길 수 있다. 예를 들어 key값 "이름"과 "나이"가 해시테이블에 같은 해시코드로 저장된다면, "이름"을 호출했는데 "나이"에 해당하는 데이터가 같이 나오게 되는 것이다. 이를 위해 해시함수는 중복되지 않게 나름의 해시알고리즘을 이용해 중복을 최소화한다. 하지만 이렇게 해시 알고리즘을 사용해도 중복은 생길 수 있다. 이런 상황을 충돌이라고 한다. 이를 해결하기 위해 방법을 알아본다.

• chaining 기법 : 충돌이 발생할 경우 해당 버킷을 링크드 리스크로 연결한다.
• linear probing 기법 : 충돌이 발생할 경우 다음 인덱스로 넘어가 저장을 시도한다. 만약 또 충돌이 발생한다면 다음 인덱스로 넘어가 시도를 반복한다.