Hash

[ hash table (or hash map) ]
– associated array: (key, value) 형식의 data를 저장하는 data structure
– hash function을 사용하여 입력 key 값으로부터 hash value를 얻은 다음 이를 index로 사용하여 associated array의 형태로 저장하는 자료구조
– hash table의 각 원소: bucket 또는 slot

[ hash function ]
– 임의의 길이를 갖는 data를 고정된 길이의 data로 mapping하는 algorithm
– input: key value
– output: hash value
– 이상적인 hash function의 조건: (A’s key value) != (B’s key value) 이면 (A’s hash value) != (B’s hash value)

[ hash collision ]
– 두 개 이상의 서로 다른 key값이 동일한 hash value로 mapping될 경우 발생

[ hash collision을 해결하는 방법 ]
– closed hashing: 처음에 주어진 hash table의 공간 안에서 문제를 해결하는 방식
– open hashing: 처음에 주어진 hash table의 공간 밖에 새로운 공간을 할당하여 문제를 해결하는 방식

[ hash search ]
– chaining: 각각의 hash table index에 해당하는 자료구조를 linked list로 만들어서 관리하는 방법. bucket 내에서는 원하는 항목을 찾을 때 linked list를 순차 탐색
– 이상적인 hash size일 경우 만약 서로 다른 key 값이 서로 다른 hash value (index)로 mapping될 경우 hash table 조회에 걸리는 시간은 상수시간

답글 남기기