Hash

• 검색과 저장이 아주 유용한 구조
• 순서, 관계 없는 데이터 빠르게 찾을 수 있음
• 데이터의 삽입, 삭제, 검색 모두 O(1)의 시간 복잡도
  • 하지만 공간 복잡도 높음
• key와 value 쌍으로 데이터 저장
• Java : map
• Python : dictionary

해시 함수 - Hash Function

• 임의의 key 값을 입력 받아 해시 함수 이용해 고정된 길이의 해시 값으로 변화
  • 해시 값을 이용해 value 위치 찾음

해시 테이블 - Hash Table

• key와 value 쌍인 데이터가 저장되어 있는 테이블
• 버킷(bucket), 슬롯(slot)이 모여 있는 형태

해시 충돌 - Hash Collision

• Chaining
  • 동일한 Bucket에 저장된 순서대로 value를 연결리스트 형태로 저장해 관리
  • 기능들의 시간 복잡도 O(n)까지 늘어날 가능성 크다
• Open Addressing
  • 무조건 하나의 bucket에 하나의 value 저장
  • 종류
    • linear probing
      • 바로 옆 bucket을 순차 탐방해 빈 곳 찾음
      • 데이터들 특정 위치에만 밀집하는 Clustering 발생
    • quadratic probing
      • n^2을 건너 뛰어 빈 공간 찾음

구현

• python의 경우 딕셔너리

# 1
hash = dict()
# 2
hash = {}
# hash[key] = value, key는 튜플, str, int 상관X, dic, list는 불가
	# index로 변환 불가하기에 사용 불가
# value도 list, dic, str, int 상관X
# pop, data 반환 후 삭제
hash.pop(key) 
# del, data 삭제(반환X)

• dic + 반복문

hash.keys()     # 모든 key list로 반환
hash.values()   # 모든 value list로 반환
hash.items()    # 모든 key, value (tuple, list)로 반환

• dic 정렬

sorted(hash)    # list 반환
				# default : 오름차순
                # 내림차순의 경우 lambda 부호반대 or 반복문 반대 이용
                		# 튜플의 경우(items())의 경우는 부호 반대 불가, index 지정해줘야한다 따로
sorted(hash.keys(), key = lambda x: x)
sorted(hash.keys(), key = lambda x: -x)
sorted(hash.values(), value = lambda x: x)
sorted(hash.values(), value = lambda x: -x)
sorted(hash.items(), item = lambda x: x)
sorted(hash.items(), item = lambda x: -x[1])