해시테이블1

• 

  210630 해싱(Hashing ) 해시 테이블(Hash Table) 찾고자 하는 원소의 키값을 해시함수를 통해 해시 값을 계산하여 그 원소가 저장된 장소를 찾아내는 방법 해시 함수(Hash Function) 모든 가능한 키 값의 집합이 U 라 하고 해시 슬롯의 갯수가 m인 경우 충돌(Collision) : 두 키값의 해시 값이 같을 때 => 충돌 발생시 해결 방법이 효율성을 좌우함 충돌 해결법 연결리스트를 이용한 방법 (Chaining) 오픈 어드레싱(Open addressing) 연결리스트를 이용한 방법 (Chaining) 평균적인 경우 : Simple uniform hashing을 가정시 (각각의 키값이 특정 슬롯에 할당될 확률이 다른 키의 할당에 상관없이 동일하다는 가정) n을 키값의 갯수라고 하고 m을 슬롯의 갯수라고 할 때, 각.. 미가공 필기(알고리즘) 2021. 7. 2.