자료구조/해시 테이블(Hash Table) (2) 썸네일형 리스트형 [자료구조] 해시 테이블 충돌 해결 기법 - 코딩밥상 해시 충돌 해결 기법 해시 테이블의 충돌을 해결하는 방법에는 크게 두 가지가 있습니다. 하나는 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 것이고, 또 다른 하나는 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결하는 것입니다. 전자는 개방 해싱(Open Hashing)이라고 하고, 후자는 폐쇄 해싱(Closed Hashing)이라고 합니다. 체이닝(Chaining) 이란? 체이닝이란 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법입니다. 체이닝이라는 이름은 충돌이 일어날 때마다 데이터를 링크드 리스트에 사슬처럼 엮는다는 의미에서 붙여진 것입니다. 체이닝 기반 해시 테이블은 데이터 대신 링크드 리스트에 대한 포인터를 관리하고 데이터는 .. [자료구조] 해시 테이블(Hash Table)과 해시 함수(Hash Function) - 코딩밥상 해시 테이블(Hash Table)이란? 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘입니다. 데이터를 매개 변수로 하여 해시 함수를 거치면 해당하는 주소가 할당되고 그 주소가 인덱스로 사용되는 것입니다. 즉 데이터가 해시 함수를 거치면 테이블 내의 주소(인덱스)로 변환합니다. 다시 한번 정리하자면 데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소에 데이터를 담는 것이 해시 테이블의 기본 개념인 것입니다. 특이하게도 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있습니다. 해시 테이블의 성능은 공간을 팔아 얻어낸다고 생각하면 되겠네요. 해시가 어떻게 데이터로부터 테이블 내의 주소값을 뽑아내는지 다음 .. 이전 1 다음
