[Algorithm & Data Structure] Hash Table

// "Normad Coder의 알고리즘과 데이터 구조 강의" 듣는 중//

​

오랜만에.. 데이터 구조..

정처기도 따야 하는데..

요새 정말.. 너무 게으르다.

 

---

Hash Tables

• 매우 중요한 자료구조
• Key Value System을 이용하여 자료를 정리.
• 예, 사전 ; 단어를 찾고 = key, 해당 단어의 뜻과 설명 = value

​

• array는 선형 검색이라서 오래걸림. --> O(n)
• => name을 하나씩 비교해야 해서 n수가 증가하면 오래걸림

​

• hash table은 key랑 value만 있어서 --> O(1)
• => 어떤 메뉴를 찾아도 소요되는 스텝은 1개
• array보다 엄청 빠름.

• array보다 value로만 작업하는 걸 선호함.

• true가 value가 되는 것

• 그러면 태국 찾는데 딱 1스텝만 필요함
• hash table은 이미 많이 사용 중이라 굳이 배우지 않아도 사용 가능함.

​

​

Hash Tables 원리

• 사실 array 구조가 hash table 안에 있음
• --> 그러면 똑같이 인덱스부터 보는 데 왜 빠를까? hash function 때문

• 저장하고 싶은 key를 숫자로 바꿈. --> 숫자가 인덱스가 되고 거기에 value가 저장됨

​

• 예시, 10개의 아이템이 있는 배열을 만들기.
• 피자 가격을 정하기 위해서 hash function을 만듦.

• pizza를 가져다가 알파벳 개수를 셈. --> 5개 => 배열 5번째에 pizza가격 저장??

• 피자 가격은 pizza= key를 찾아서 hash function에 넣으면 해시 펑션이 5를 줄거고 index 5로 가면 피자 가격임.
• 만약에 cake이면 key를 해시함수에 넣고 해시 펑션이 준 4에 가격(value)이 저장됨. 리스트의 4번째 가격이 바로 출력
• ​
• 알파벳 수가 겹치면?? like, taco !! 4..
• --> hash collision 해시 충돌
• => 각기 다른 key에 해시함수가 동일한 숫자를 준 경우
• => 배열 4번 째 공간에 또 배열 넣기.

• cake = key 입력시 해시펑션에서 4받고 배열에서 4번째로 이동 후에 "4번 째 공간에서 cake 찾을 때까지 선형검색"

​

• so, 항상 상수 검색은 x, 충돌이 생기면 선형검색을 해야 함.
• 그런데 전반적인 평균 시나리오 중심으로 판단해야 하고 그렇게 보면 시간복잡도는 O(1)임.
• --> 이미 프로그래밍 언어에 들어가 있기 때문에 굳이 만들 필요도 없음. 그냥 원리만 알아둘 것.