Hash Table key값은 불변!

 

이 글은 아래 유튜브 "코딩 국수" 님의 영상을 보고 생각한 점을 작성합니다.

 

https://youtu.be/ET3iI5bNM80?si=B48M_fPSzaL3FKEI

 

 

언젠가 파이썬 딕셔너리를 활용하며 왜 안되지?

라는 생각을 한 적이 있다.

이러했던 경험을 논리적으로 풀어보려 한다.

(자바에서는 HashMap과 동일하다)

 

딕셔너리는 아래와 같이, key와 해당 key에 해당하는 value값으로 구성되어 있다.

dic = {"123": 12345}

 

 

이는 조금 더 풀어보면, "key의 해시값에 해당하는 위치에 value 값을 저장"하며

덕분에 key값을 알면, value값에 접근하는 시간을 O(1)의 시간으로 줄여준다.

이러한 구조를 해시 테이블(Hash Table)이라 칭한다.

 

"key의 해시값" 이라는 것이 뭘까?

이는 곧 정해진 key 값에 대해 어려운 함수 알고리즘을 통해 어떤 수학적인 값을 내는 것이다.

예를 들어 key가 "key123"이라면, 이 key123을 어려운 함수 알고리즘을 통해 13409239775 와 같은 값으로 변환하고

13409239775 위치를 본다면, 내가 저장한 value값이 있게 되는 구조이다.

 

 

이 알고리즘의 특징으로는 최대한 겹치지 않게 key값이 변환되어야 한다.

value를 저장할 위치가 겹치는 상황이 나오면 안되기 때문이다.

이런 상황에 대비해

1. chaining 혹은 2. 다음 주소에 저장 하는 등의 방식이 있지만, 해당 글과는 조금 벗어나기에 넘어가겠다.

 

 

머 결국! 글의 주제로 돌아가서, HashMap, Dictionary, Hash Table의 key값을 왜 불변해야 하나?

 

바로 내가 설정한 key값의 함수 알고리즘을 통해서 나오는 결과가 달라지기 때문이다.

이 값이 달라지면, 함수 알고리즘을 통해 value값이 있다고 가리키고 있는 공간이 달라지고

기존에 존재했던 value의 값은 남아있게 되기 때문이다.

 

따라서, HashMap, Dictionary, Hash Table의 key 값은 불변하는 값이어야만 한다.

 

 

끗~