[iOS] HashTable, Dictionary

HashTable, Dictionary

다른 언어를 공부하는 친구들이 HashTable을 말할 때

스위프트를 공부하는 저는 Dictionary를 생각했습니다.

해시란 뭘까?라는 질문에 Dictionary에서 사용하는 키값!! 유일한 키값!! 이라고 생각을 했습니다. (Set에서도)

조금더 파고 들어봐요.. hash란 Swift라는 언어에서 이 hash를 어떻게 이용하는지

 

스위프트의 Dictionary는 어떻게 구현 됐을까?

Dictionary의 내부는 배열로 구성되어 있다고 해요.

hasher라는 함수로 데이터를 인덱스화 시켜주고 그 인덱스로 배열에 접근하게 되는거죠!

그래서 딕셔너리의 시간 복잡도는 중복이 안나면 O(1)이 됩니다.

 

이러한 해셔함수로 만든 인덱스가 중복 된다면 ??!

 

대표적으로 두가지 기법이 있어요.

 

1. 체이닝 기법

연결리스트를 이용하여 데이터 뒤에 추가로 연결 시켜서 저장하는 기법을 말함.

 

2. 선형 기법

충돌이 일어날 경우 해쉬 주소값을 순회하여 가장 처음 나오는 빈 공간에 저장하는 기법

여기서 Swift는 선형 기법을 사용하게됩니다. 선형! 선형!! Linear!! 기억해 선형 리니어 라이너 아무튼!

 

개발을 하면서 더욱 만나게 되는 Hash

Custom으로 만든 구조체를 Dictionary의 Key값 또는 Set의 Value값으로 넣으려고 하다보면 Custom구조체에 Hashable 프로토콜으 체택하라는 경고창이 뜨게 됩니다.

이 때 == 같은지 비교하는 연산자를 요구하게 되는데요 !!

 

이유는 !!

Key값이 수없이 무한정 들어오면 중복이 되는 경우가 분명 생길거에요.!! 이 경우에 스위프트는 해당 메모리의 다음 빈 메모리에 키값을 저장하는 Linear한 방법으로 중복을 해결하는데요!

이러한 값을 비교하게 될떄 == 연산자를 사용하게 되기 때문입니다.!

 

스위프트 컬렉션 타입을 공부하면

딕셔너리를 배울 때 순서가 보장되지 않는다고 하는데 이제 이게 왜 보장되지 않는지 !! 알겟죠!!

배열처럼 입력 순서에 대한 보장을 해주지 않아요. 왜냐!! 딕셔너리 내부의 인덱스 값으로 순서를 매기기 때문이죠!

 

실험

딕셔너리를 만들고 출력을 해볼까요!! 

 

왜 for 문을 10번했냐 하면 이것은 엘레베이터 닫힘을 계속 누르는 저의.. 읍읍 ㅋㅋ  장난이구 반복문에 의해 영향을 받을까.. 싶어 소심하게10번 반복해봤어요..

 

 

만약 여기서 새로운 값을 추가한다면 위 print된 순서에서 새로운 값이 insert 되겟죠?! 

좋아~~~~~ 위의 순서에서 제가 새로 추가한 333 키값이 삽입 됐네요. ㅎ 

 

 

그란데 말입니다. Grande is Horse

Set에선 좀 달라요.. 

 

 

으이이이잉?

셋도 Hashable을 쓰는데 .. 배열에 넣고 인덱스화 하는 느낌이 아닌가.. 

 

혼자서 아 Dictionary도 배열로 되있으니까 Set도 배열로 되어있겠지 했는데.. 아니었습니다.

(친구말론 트리로 만들어 진걸 수도 있다. 라고 하네요..) 언어마다 다르게 구현됐을 수 있다아아아!!

 

의문

셋은 값을 새로 추가하면 위치가 바뀜 근데 딕셔너리는 기존의 순서를 보장하면서 새로 추가가 됨.

아 잠시만 그러면 딕셔너리안이 배열로 되어있다면... 데이터가 하나만 들어가 있는데 그 해시 키값의 인덱스가 100000이면 100000의 배열 사이즈를 가지게 되는건가 ..

 

애플뇨속들 내부를 어떻게 만든거지

 

후기

개발을 공부하면서 생소한 단어들이 되게 많다. 처음엔 hash가 뭔지도 몰랐다구..

동작을 생각하면 되게 쉬운 것들인데.. ㅋㅋ 일단 모르는 단어고 기법이어도 부딪히는거에요 ㅋㅋ 언젠간 깨달음을 얻습니다.