해시 (Hash)와 람다 (Lambda)

해시 (Hash)

• 키 (key)와 값 (value)를 매핑하여 데이터를 저장하는 자료구조
  (python에서는 기본으로 제공되는 딕셔너리 자료형이 해시 테이블의 구조)
• 해시 테이블은 해시 함수를 사용해 색인 (index)을 버킷 (bucket)이나 슬롯 (slot)의 배열로 계산
• 데이터를 다루는 기법 중 하나로 데이터 검색과 저장이 빠르게 진행
• 용어
  • 키 (key) - 고유의 값으로 해시 함수의 input이고, 다양한 길이를 가짐
  • 해시 테이블 (Hash table) 또는 해시 맵 (Hash map) - key 와 value를 매핑하여 데이터를 저장하는 자료구조
  • 해시 함수 (Hash function) - 임의의 값을 고정된 길이의 데이터로 변환하는 함수.
    다양한 길이의 키를 고정된 길이의 해시로 변환하여 저장소에 저장
  • 해시 (Hash) - 해시 함수의 output으로 해시 값과 매칭되어 버킷에 저장
  • 해시 값 (Hash value) or 해시 주소 (Hash address) - 키에 해시 함수를 적용하여 얻는 해시 값
  • 버킷 (Bucket) 한 개의 데이터를 저장할 수 있는 공간

---

Keys	Hash function	Hash value	Bucket
John		01	123-4567
Smith		03	123-7896
Joanah		17	123-2103

 

위의 표에서 보면 다양한 길이를 갖는 Key 값에 Hash function을 적용해 고정된 길이의 데이터(01, 03, 17)로 변환

이렇게 변환된 데이터가 해시 값 (Hash value)이고 버킷에는 키와 매핑된 원래 데이터가 저장

결론 - 변환된 키 값과 버킷에 매핑되어 있는 데이터를 해시라 하고 이러한 자료 구조를 해시 테이블이라고 한다

---

• 특징
  • 시간복잡도가 O(1)로 데이터 저장 및 읽기 처리 속도가 매우 빠름
    (배열의 인덱스처럼 해시 함수를 통해 얻은 키 값으로 위치 탐색)
  • 하지만, 무조건 O(1)의 복잡도를 갖는 것은 아님
  • 최악의 경우 O(n)의 복잡도를 갖는데, 이유는 충돌 (collision) 때문

---

• 충돌 (collision)
  • 여러 개의 키 값이 해시 함수를 통해 같은 해시 값을 갖는 경우
• 해결 방법
  • Chaining - 충돌 발생 시 버킷에 연결리스트 자료 구조를 통해 데이터를 연결하여 해결
  • Open Addressing - 충돌 발생 시 빈 버킷을 찾아 데이터를 저장
    • 선형 탐색 (Linear Probing) - 충돌 발생 시 해당 위치부터 순차적으로 버킷을 하나씩 탐색
      (02번에서 충돌이 발생하면 순차적으로 03, 04... 로 버킷을 옮겨 빈 버킷에 데이터 저장)
    • 제곱 탐색 (Quadratic Probing) - 충돌 발생 시 해당 위치부터 제곱만큼 떨어진 다음 버킷 탐색
      (1, 4, 9, 16, 25....)
    • 이중 해시 (Double Hashing) - 충돌 발생 시 다른 해시 함수를 한 번 더 적용

---

람다 (Lambda)

• def를 사용해 필요한 함수를 생성하지 않고, 간단하게(?) 사용하기 위해 만들어진 함수
• 선언방법

lambda 매개변수(x) : 표현식

• Ex _ 두 수를 더하는 함수

def plus(x, y):
    return x + y
    
plus(10, 15)
#===================
30

# Lambda 형식 표현

(lambda x, y : x + y)(10, 20)

#===================
30

---

• map()
   - map(함수, 리스트) 의 형태
  • map은 함수와 리스트를 인자로 받는 함수
  • 리스트로부터 원소를 하나씩 꺼내어 함수를 적용한 후, 결과를 새로운 리스트에 담아줌

# 0 ~ 4까지 제곱
map(lambda x : x ** 2, range(5))

# [0, 1, 4, 9, 16]

list(map(lambda x : x ** 2, range(5)))

# [0, 1, 4, 9, 16]

---

• filter()
   - filter(함수, 리스트)
  • 리스트에 들어있는 원소들을 함수에 적용시켜 결과가 참인 값들로 새로운 리스트를 만들어줌
    (0부터 9까지 리스트에서 숫자를 하나씩 꺼낸 후, x < 5가 참이면 새로운 리스트에 넣어 반환)

# 0 ~ 9까지 리스트 중 5보다 작은 것만 return

filter(lambda x : x < 5, range(10))

# [0, 1, 2, 3, 4]

list(filter(lambda x : x < 5, range(10)))

# [0, 1, 2, 3, 4]

# 홀수 반환 필터

filter(lambda x : x % 2, range(10))

# [1, 3, 5, 7, 9]

list(filter(lambda x : x % 2, range(10)))

# [1, 3, 5, 7, 9]