Lesson4 Maps and Hashing

1. map은 일종의 Key-Value 구조이다. Key로 찾고, Value에 값을 저장한다.

 

2. Set은 List와 비슷하지만 조금 다르다. Set은 리스트와 다르게 순서가 없으며, 중복을 허용하지 않는다.

2-2. Key는 유일해야한다. Definition은 여러가지일 수도 있어도 말이다. 즉 키는 맵 상에서 유일하다.

 

3. 이제까지는 어떤 아이템을 찾는데, 모든 아이템을 다 뒤져봐야 했기 때문에 시간은 아이템 수에 비례해서 증가하였다.

3-2. Constant time look-up은 당신의 작업을 엄청나게 빠르게 해줄 것이다. Hash Function을 사용하세요!

 

해쉬 퐁션을 배우게 된 것을 이 강아지가 축하해 주었다.

4. 해쉬 퐁션의 목적은 값을 쉽게 저장 되며 불러올 수 있는 값으로 변환하는 것이다.

 

4-2. Hash Function의 특징 중 하나는 어떤 수를 상수로 나눈 뒤 끝자리 몇을 취하는 방식이다. 또 몫으로 어레이의 자리를 정한다.

 

 

5. 만약에 같은 위치에 해쉬 값이 저장된다면? 이러한 현상을 Collisions라고 한다.

 

5-1. 첫번째 방법은 해쉬 함수 안의 값을 고치는 거나, 해쉬 함수 자체를 바꾸는 것이다. 이 방법으로 충분한 슬롯을 얻을 수 있다.

 

 

5-2. 두 번째 방법은 해쉬 함수를 유지하면서, 배열의 구조를 바꾸는 것이다. 예를 들자면 슬롯을 리스트로 만드는 것이다. 이런 방법을 일반적으로 버켓이라고 부른다.

 

 

5-3. 첫 번째 방법은 충돌 시마다, 확장을 시킨다면 공간적으로다 시간적으로 비용이 발생한다. 두 번째 방법도, 배열의 크기가 상당해지만다면, 이것 역시 해쉬로 한 이유가 없어지게 된다.

 

5-4 해쉬의 해쉬도 있다고 하니, 상황에 맞춰 잘 사용해야 한다.

 

6.

 

Load Factor = Number of Entries / Number of Buckets

Load Factor를 사용하는 이유는 이용률을 확인하기 위해서다. 1에 가까울 수록 효율적인 해쉬 사용률이라는 뜻이다.

 

7. 해쉬 함수는 키를 저장하기 위한 함수였지만, 해쉬 맵은 그 위치에 키와 값을 같이 저장한다.

7-2. 해쉬 맵은 알고리즘과 융합하기에 아주 유용하다. 해쉬 맵이 속도를 아주 빠르게 하기 때문이니, 데이터 구조에 대해서 생각할 때 해쉬구조를 가장 먼저 생각해야 한다.

 

7-1. 문자열 키 이 해싱 시스템의 진정한 아름다움은 문자열 키도 사용할 수 있다는 것이다. 이 때, 문자를 숫자로 바꿔 주는 해쉬 함수가 필요하다. 문자 하나는 아스키 코드를 통해 쉽게 숫자로 바뀔 수 있다. 똬 아스키 값을 특별한 해쉬를 얻기 위한 공식과도 결합할 수 있다.

 

7-2. 문자가 30개 이하라면, 단어의 첫번째 문자를 해쉬 값으로 사용 할 수 있다. 요런 식으로 아스키 코드와 공식을 이요하면 해쉬 값을 얻을 수 있다. 하지만 3~4개의 문자를 해쉬 값화 시킬 경우 공간을 상당히 차지하게 된다.

7-3. 31은 해쉬 값을 만드는 괜찮을 발견이었다. 일종의 전통이다. 하지만 요즘에는 조금 더 복잡한 해쉬 함수가 발견되고 있다. 나의 해쉬값을 찾는 것이 중요하니, 게으르지 말라!

Hash Value = (ASCII Value of First Letter * 100) + ASCII Value of Second Letter