Python/Data Structure1 해시 테이블(hash table) (1) 개념 해시 테이블은 자료구조 중 하나로 매우 빠른 평균 삽입, 삭제, 탐색 연산을 제공한다. 파이썬을 기준으로 작성하기 때문에 딕셔너리로 비유하면, key 와 value를 가지고 있는 형태의 데이터를 가지고 있다고 가정을 해보자. 이 데이터를 해시 테이블에 넣을 때 몇 번 인덱스에 저장할 지를 고민한다.이때 필요한 것이 해시 함수(hash function)이다. 해시 함수는 key의 정보를 hash table에 매핑한다.간단한 예시로는 key에 len(hash table)을 나눈 나머지로 hash table의 인덱스에 매핑하는 방법이 있다. 그러나 만약 두 데이터가 매핑한 인덱스가 같은 값이 나오는 경우가 있다.이런 경우를 충돌(collision)이라고 한다. 충돌은 되도록 없는 것이 좋지만, 완전히 없는건 .. 2024. 7. 8. 이전 1 다음