HashTable 해시테이블 클래스

[ks2colorworld]

• open addressing :
  • [x] linear probing https://github.com/ks2colorworld/Data-Structures-In-Python/issues/9#issuecomment-1859543561
  • [ ] quadratic probing https://github.com/ks2colorworld/Data-Structures-In-Python/issues/9#issuecomment-1859579927
  • [ ] double hashing https://github.com/ks2colorworld/Data-Structures-In-Python/issues/9#issuecomment-1859713846

• [x] chaining https://github.com/ks2colorworld/Data-Structures-In-Python/issues/9#issuecomment-1859725569

• 영상링크 : 자료구조 해시테이블 - 소개, 해시 함수

[ks2colorworld]

• 영상링크 : 자료구조 해시테이블 - open addressing (linear probing)

[ks2colorworld]

• 영상링크 : 자료구조 해시테이블 - 성능평가, chaining

[ks2colorworld]

• 챗지피티

파이썬은 해시 테이블을 기반으로 하는 많은 내장 클래스와 데이터 구조를 제공합니다. 그 중에서도 가장 널리 사용되는 것은 다음과 같습니다:

1. 딕셔너리(Dictionary): 파이썬의 딕셔너리는 키-값 쌍을 저장하는데 해시 테이블을 사용합니다. 따라서 딕셔너리는 빠른 검색과 삽입을 제공합니다.
2. 셋(Set): 셋은 고유한 값을 저장하는데 사용되며, 이 역시 해시 테이블을 기반으로 합니다. 셋은 중복된 값을 허용하지 않으며, 집합 연산에 유용합니다.
3. collections 모듈의 defaultdict: collections 모듈에서 제공하는 defaultdict 클래스는 딕셔너리와 유사하지만, 기본값(default value)을 가지고 있습니다. 내부적으로도 해시 테이블을 사용합니다.
4. collections 모듈의 Counter: collections 모듈에서 제공하는 Counter 클래스는 해시 가능한 객체의 개수를 세는데 사용됩니다. 이 역시 내부에서 해시 테이블을 활용합니다.

이 외에도 파이썬의 내장된 다양한 컨테이너 및 자료 구조들이 해시 테이블을 사용하여 구현되어 있습니다. 해시 테이블을 기반으로 하는 이러한 자료 구조들은 빠른 검색과 삽입 연산을 가능하게 합니다.

[ks2colorworld]

• 해시 함수 : 겹치지 않는 고유한 값을 생성하도록 설계
• 해시 테이블 : 해시 함수를 사용하여 데이터 규칙(해시 값)을 적용하여 데이터를 효과적으로 저장, 검색할 수 있는 자료구조
• https://c4u-rdav.tistory.com/18

[ks2colorworld]

• perfect hash function
• universal hash function
  • hf(x) == hf(y) = 확률이 1/m --> c/m (c-universal h.f)
• 해시함수의 종류
  • 
  • 

[ks2colorworld]

• 코드 작성하면서...

• k<i<=j가 아니라 k<=i<j 인 것으로 판단됨.

[ks2colorworld]

• 위의 3 경우를 모두 확인하기 위해서

• if i<k: i2=H.size+i, if j<k: j2=H.size+j (i,j 값을 보정한 후)

• k<i2<j2 조건을 만족하는지 확인한다. (k<i2<=j2 혹은 k<=i2<j2)

• k < i and i <= j 1 조건에 2,3 조건 추가 - commit : https://github.com/ks2colorworld/Data-Structures-In-Python/commit/dbfb6393fcc322b408da08d71fff454e30825bef#r135211221

• if k < i and i <= j :
• if k < i and i <= j or \
• i <= j and j < k or \
• j < k and k <= i:

[ks2colorworld]

• open addressing : linear probing (move to the next slot) - commit : https://github.com/ks2colorworld/Data-Structures-In-Python/commit/dbfb6393fcc322b408da08d71fff454e30825bef#r135211413

[ks2colorworld]

• quadratic probing 제곱

[ks2colorworld]

• double hashing 두개의 해시함수 사용

[ks2colorworld]

• chaining

[ks2colorworld]

• 구현해 보면서 개념을 이해하는 것에 의미를 가지고

• 실제로는 사용하는 언어의 라이브러리에서 제공하는 hash table을 사용한다.