해시 테이블

https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

해시 테이블

Key & Values

- 해시 테이블은 value와 key를 가짐

- 딕셔너리와 다른 점은 key가 계산된 숫자 시퀀스 혹은 char

- 배열을 사용해서 연속적이지 않은 buckets라고 불리는 구조에 저장

- 각 값의 위치는 해시 함수에 의해 계산

 

해시 충돌(collisions)

다른 값을 input 했지만 같은 hash값을 가지는 경우(다른 값이라도 같은 해시를 가질 수 있지만 같은 해시 값이라 해서 같은 인스턴스는 아님 -> 단방향)

 

해시의 장점

중복을 허용하지 않기 때문에 중복되지 않는 데이터 값을 가져야 하는 구조에서 사용할 수 있다.

특히 그 크기가 어떻든 간에 값을 찾는 시간 복잡도가 O(1)이기 때문에 크기가 큰 데이터에서 값을 효과적으로 찾을 수 있다.

 

딕셔너리를 사용한 이유

딕셔너리는 키에 값이 들어 있는 경우 값을 반환하지만 get()을 사용하는 경우 key에 값이 없을 때 false를 반환함.

이를 사용하여 배열을 정렬하지 않고 원하는 값을 찾아내기 위해 사용함

그러나 중복된 이름을 가지는 사람이 있어 리스트 자체를 비교하는 것도 좋은 방법이었다.

 

새롭게 알게 된 것

import collections

collections.Counter(이터레이터형 객체) -> 서로 연산 가능

 

hash() -> 해시 값 반환