카테고리 없음

Module 7 - HashMaps

쭈니123 2023. 7. 10. 10:00
왜 HASHMAP?

 

search 를 O(1) 으로 하기 위해서

Maps?

key

같은 key 가 다른 value 를 가져올수 없다. key 를 이용해 문을 열면 물건이 무조건 하나여야 함 
비슷한 이유로 key 는 바뀔수 없다 

value

value 는 겹쳐도 됨. key 1, key 2를 이용해 방에 들어가지만 물건이 둘다 사과일수 있는 느낌
같은 이유로 value 는 바뀔 수 있다.

예시) 휴대폰 번호 = key 사람이름 = value / 번호마다 사람은 한명이지만 다른 번호를 가진 같은 이름이 있을수 있다.

++ value 는 무슨 type 이든 될수 있음

HASH MAP HASH TABLE 차이

Hash Maps allow null keys and values. Hash Tables do not allow for the use of null
Hash Tables are thread safe because they are synchronized.Hash Maps do not synchronize.
Hash Maps use iterator to iterate through its object values.Hash Tables use enumerator.
Hash Maps are much faster and use less memory than HashTables.

MAP ADT

  • V put (<k, v>) = 새로운 key-value 삽입. 원래 value 가 있으면 업데이트 하고 원래 value return. 원래 없었다면 null return
  • V get (k) = k 에 따른 value 가져옴
  • V remove(k) = k 에 따른 value 삭제

hashmaps

Index calculation

  • hash code 가 234413 이면 index 를 그만큼 만들 수 없기 때문이다
  • a % n (n = length)

compression 이후에 key 가 같아지는걸 collision 이라고 부른다.

avoiding collison - resize

External chaining

아까 예시에서 61 이 두개였으니 GF 를 새로운 head 로 받아서 연결한다 addToFront in linkedlist 61

 

이렇게하면 index 가 부족할 일은 없지만 한 linkedList 에 너무 많아지면 runtime 이 길어지므로 resize 를 한다

resize 할때 그대로 복붙하지 않게 조심

Linear Probing

external 과 다르게 index 마다 entry 가 하나이다
말그대로 자리가 있을때까지 계속 +1
순서대로 숫자 % length 를 해서 넣고 이미 있다면 다음거에 넣은 모습이다
index = 1 으로 가서 1인지 확인후 없으니 다음껄로 넘어가는 모습
삭제한 후 DEL 로 채워줘야함, 나중에 get 등으로 probing 할때 끊기지 않기 위해서
index 1 부터 4까지 돌고 5 가 null 이기 떄문에 멈춤
put method
SAVED DEL 이 저장되면 index 5 대신에 그곳에 넣을수 있음
Del do not count as a load factor

Quadratic Probing

이미 있으면 1^2 한칸 가고 또 있으면 2^2 ... so forth
계속 가다가 length^2 까지 가면 멈춘다

 

Double Hashing 

이해가 어려우니 예시: 8 을 빈자리가 있으니 넣고 1이 들어가야하는데 자리가 없음

그럴때 idx + c*1 사용해서 해결. C = 5 - H(1)% 5 여기선 prime number q < length 를 5로 지정해준것

그래서 원래 index 1 + 4 = 5 index 5 로 들어감

 

BIG O

  • Implementations using either arrays or linked list are easy, and both result in O(n) search performance.
  • Depending on the key, performance can be reduced toO(log n))
  • .If keys were like an index in an array, then access can be achieved in O(1)
  • if keys give a variety of different hash codes for different objects adding, searching, and removing from a hash map is O(1).
  • If the keys have a limited range of hash codes, or collisions occur for other reasons, then adding, searching, and removing from a hash map is O(n).
the capacity of the map is N, and indices range 0 to N − 1.
In order to use the hash code, keys must be converted to integers, if not already integers.
If the integer keys are not in the given range (0 to N − 1), then a HASH function is used to map the keys to
corresponding indices in a table.

For all questions, state the WORST case time complexity of performing each operation on the given data structure.

BST

  • height: O(n)
  • add: O(n)
  • remove: O(n)
  • search: O(n)

Hash Map with External Chaining

  • add: O(n)
  • remove: O(n)
  • search: O(n)

Heap

  • add: O(log n) (amortized). O(n) in the worst case.
  • remove: O(log n)
  • search: O(n)