[Datastructure]Hash Table
2020. 2. 7. 15:11
Hash Table Hash Table은 key 를 이용하여 value를 저장하고 가져올때 빠르게 가져올수 있는 자료구조이다. 해시함수에 key값을 input으로 주면 해시함수에서 어떤 특정한 값을주게 된다. 그 값을 array의 index로 사용하여 값을 저장하게 된다. 이렇게 되면 같은 값으로 data를 찾을때 시간복잡도가 상수시간을 따르기때문에 매우 빠르게 검색이 가능하게 된다. 해시충돌 Separate chaining 방식 해시테이블은 다른 key값을 넣어도 같은 해시값을 가지고 동일한 array의 index으로 값을 넣어버릴수가 있다. 이렇게되면 이전값은 새로 온 값에 아마 지워질것이다. 이런 문제를 해결하기 위해 해시태이블에 array의index값에 새로운 노드를 만들어 linked list ..
