해시테이블

[C#] 자료구조 : 해시테이블 (Hash Table)

해시(Hash)는 키 값을 해시 함수(Hash function)으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다. 키 값을 통해 직접 엑세스하기 위해서 모든 가능한 키 값을 갖는 배열을 만들면, 배열크기가 엄청나게 커지게 된다. 예를 들어, 주민등록번호를 키 값으로 하는 경우, 000000-0000000 부터 999999-9999999까지 10의 13승의 배열 공간이 필요한데, 만약 회원수가 1000명인 경우, 1000명을 저장하기 위해 10^13의 엄청난 배열 공간이 필요하게 된다. 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용하게 되는데, 이 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다. 하지만 경우에 따라 서로 다른 키가 동일한 해시테이블 버켓 위치..

해시 테이블

해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다. 해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다. 해시 함수(Hash Function)을 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Function) 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)으로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에 사용되는 대표적인 해시 알고리즘에는 ..