hashTable이란 ?

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
출처: https://mangkyu.tistory.com/102 [MangKyu's Diary]

SimpleHashTable

먼저 해시테이블의 헤더파일을 구현하고 분석 하였다. 충돌이 일어나지 않는다는 가정 하에 만든 해시 테이블이기 때문에 NODE의 구성은 매우 간단하다. 연결 리스트가 사용되지 않기 때문이다.

다음으로는 간단한 해시테이블의 함수들을 구현하고 분석해 보았다.
해시 함수를 통해서 address값을 구한다.
새로운 해시테이블을 생성할 때 테이블 사이즈 만큼 노드를 추가한다.
새로운 값이 들어올 때마다 해시함수를 거쳐서 그 인덱스(address)에 넣어준다
Get으로 그 값을 가져올 때도 마찬가지로 key 값을 거쳐 주소를 얻어내 바로 그 값을 가져온다.

이것은 메인함수이고 이 다음 장에 이 메인함수의 실행 화면을 보이도록 하겠다.

왼쪽 실행창과 같이 키 값에 따른 value값을 정상적으로 잘 가져온 것을 볼 수 있다.

ChainingHashTable

추가적으로 체이닝으로 충돌을 방지한 해시테이블을 구글링을 통해 공부하며 구현 해보았다.
이에 대한 분석은 주석으로 달았다.

여기서 table과 bucket은 같은 뜻으로 사용했다.

체이닝 해시테이블에서 값을 추가하는 코드를 구현 해보았다. 그 주소에 값이 있을 경우 새로운 값을 헤드로 사용하는 코드로 구현했다. (뒤에서부터 데이터를 삽입하는 코드는 삽입할 때마다 연결리스트를 돌아야하는 수고를 얻게 된다.)

마치며..

해시 테이블은 키 값을 해시함수를 거쳐 바로 인덱스값을 얻어오는 방식으로 O(1)의 최상의 수행시간을 얻게 된다.
물론 체이닝기법을 사용하게 되면 각각의 테이블 마다 노드의 길이가 길면 길 수록 수행시간이 조금씩 길어질 것이지만 그 정도 오버헤드로는 해시테이블의 장점을 덮을 수 없었다.
이 레포트가 끝나면 해시 테이블에 대해서 더 공부해볼 예정이다.