해시(hash/해시값) : hash는 key(다양한 길이)가 해시함수를 거쳐 반환된 값(고정된 길이)이다.
해시함수 : 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수가 반환하는 값이 해시(hash)다. 서로다른 key값이 같은 hash가 되는 것(해시충돌)을 최대한 최소화하는 것이 좋다.
해시의 시간복잡도 : 삽입(insertion), 삭제(deletion), 검색(search)의 평균적인 시간복잡도는 O(1)이다. 고유한 key값에 해당하는 hash와 매칭되는 값을 삽입, 삭제, 검색만하면 되기때문이다. 하지만 하나의 버킷에 값이 들어간다면(최악의경우), O(n)의 시간복잡도를 가질 수 있다.
key : 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다(공간의 효율성을위해 해쉬함수를 거쳐 hash로 바꿔줌).
해시 충돌 방지 방법으론 chaining과 open addressing등이 있다.
느낀 점:
해시와 관련된 개념들의 용어가 많이 헷갈렸다..! 찾아보는 자료마다 조금씩 다른 용어를 써서 더 헷갈렸다..!
키워드:
해시테이블, 해시, 해시함수, key, 해시충돌
배운 것:
해시(hash/해시값) : hash는 key(다양한 길이)가 해시함수를 거쳐 반환된 값(고정된 길이)이다.
해시함수 : 해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수가 반환하는 값이 해시(hash)다. 서로다른 key값이 같은 hash가 되는 것(해시충돌)을 최대한 최소화하는 것이 좋다.
해시의 시간복잡도 : 삽입(insertion), 삭제(deletion), 검색(search)의 평균적인 시간복잡도는 O(1)이다. 고유한 key값에 해당하는 hash와 매칭되는 값을 삽입, 삭제, 검색만하면 되기때문이다. 하지만 하나의 버킷에 값이 들어간다면(최악의경우), O(n)의 시간복잡도를 가질 수 있다.
key : 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다(공간의 효율성을위해 해쉬함수를 거쳐 hash로 바꿔줌).
해시 충돌 방지 방법으론 chaining과 open addressing등이 있다.
느낀 점:
해시와 관련된 개념들의 용어가 많이 헷갈렸다..! 찾아보는 자료마다 조금씩 다른 용어를 써서 더 헷갈렸다..!