chaining
-
해시 알고리즘알고리즘/문제풀이 2020. 9. 20. 23:00
이번 시간에는 해시 알고리즘에 대해서 알아본다. 해시 테이블과 해시 테이블에서 충돌이 발생하는 경우 해결방법 2가지를 알아본다. 1. Direct Addressing Table 크기가 U인 테이블 T를 생성하고 key k를 slot key에 저장하는 방식이다. 해당 테이블은 중복되는 키가 없다고 가정한다. 이는 삽입, 삭제, 검색 모두 O(1)이지만, 모든 키를 넣어야 하기 때문에 공간 낭비가 심하다. 예를 들어 모든 학생들에게 한 자리씩 할당해 준 것이다. 2. Hash Table key k를 저장할 때 slot k를 저장하는 것이 아니라 slot h(k)에 저장한다. key k가 slot h(k)로 해시되었다고 하며, h(k)를 key k의 해시값이라고 부른다. 이때 h( )는 해시 함수라고 부른다...