'tips of computer'에 해당되는 글 12건

  1. 해쉬 테이블 (hash table)

해쉬 테이블 (hash table)

1. 데이터를 키(key)를 가지고 검색

2. 번호가 붙은 여러개의 통(bucket) 에 데이터를 분산 저장

3. 데이터를 검색할 때는 일정한 공식에 따라 키 값을 가지고 통(bucket) 번호를 바로 계산 (따라서 검색 속도가 빠름)

4. 때로는 똑같은 데이터가 중복 저장되지 않게 만들어야 할 경우도 있는데 이럴 때는 집합(set)을 사용


현실 세계와 비교하자면


주소록 카드가 있다고 했을 때, 카드가 적으면 상관 없지만 많아지면 찾기 쉽게 하기 위해 ㄱ, ㄴ, ㄷ 으로  번호를

붙여서 관리하는 것을 생각하면 된다.


해쉬 테이블은 바로 이런 데이터 분류 체계를 모방한 자료구조이다.

1. 데이터를 넣을 여러 개의 통(bucket)을 만들어 두고, 키 값을 이용하여 데이터를 넣을 통 번호를 계산한다.

2. 데이터를 꺼낼때도 키 값을 이용해서 통(bucket) 번호를 계산한 후, 그 통 안에서 데이터를 찾는다.

3. 이것은 통(bucket) 안에서는 키 값을 일일이 비교해야 하지만, 전체 데이터의 키 값을 모두 비교하는 것보다는 훨씬

   시간이 절약된다.