Dot Algo∙ DS/자료구조
2022. 5. 5.
해시(Hash)와 해시 테이블(Hash Table)
해시 테이블 Hash Table 해시 테이블은 키를 저장하거나 해당 키와 관련된 값을 저장하는 데 사용되는 자료구조다. 삽입, 삭제, 조회가 평균 O(1) 시간에 수행된다. 기본 개념은 키를 배열에 저장하는 것이다. 배열에 저장되는 위치(슬롯)는, 키를 '해시 코드(hash code)'한 결과에 따라 결정된다. 해시 코드란 키값에 해시 함수를 적용해서 계산된 정수값을 말한다. 해시 함수를 잘 고른다면, 객체를 배열에 균일하게 분배할 수 있다. 해시 충돌 Hash Collision 1) 연결리스트를 통해 객체 저장 다른 두 개의 키가 동일한 위치(해시 코드가 일치)로 매핑되면 충돌이 발생했다고 한다. 충돌을 처리하는 일반적인 방법 중 하나는 각 배열의 인덱스에서 연결리스트를 통해 객체를 저장하는 것이다. ..
