[자료구조] Map과 Hash Table: 해시 함수와 해시 충돌의 해결, 해시 테이블 리사이징

2023. 12. 19. 17:00· Computer Science/Data Structure
목차
  1. 💋 Map ADT
  2. ✔️ 개념
  3. ✔️ 주요 동작
  4. ✔️ 구현
  5. 💋 Hash Table
  6. ✔️ 개념
  7. ✔️ Hash function이란?
  8. ✔️ 동작 방식
  9. 💋 Hash Collision
  10. ✔️ 개념
  11. ✔️ hash collision의 해결 방법 - seperate chaining (체이닝)
  12. ✔️ hash collision의 해결 방법 - open addressing (개방 주소법)
  13. 💋 Hash Table Resizing
  14. 💋 프로그래밍 언어 별 Hash Table 구현
  15. ✔️ Python
  16. ✔️ Java
  17. ✔️ C++
  18. ✔️ JavaScript
  19. 💋 참고자료
반응형
반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

 

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

주니어 개발자를 위한 전공 지식 모음.zip. Contribute to seoul-developer/CS development by creating an account on GitHub.

github.com

 

💋 Map ADT

✔️ 개념

  • key-value 쌍을 저장한다.
  • key는 중복되지 않는다.
  • associative array, dictionary라고도 부른다.

 

✔️ 주요 동작

  1. put(key, value): 지정된 키에 값을 연관시킵니다. 만약 이미 해당 키에 값이 존재한다면, 기존 값은 새로운 값으로 대체됩니다.
  2. get(key): 지정된 키에 대응하는 값을 반환합니다. 만약 키가 존재하지 않으면 예외나 특별한 값을 반환할 수 있습니다.
  3. remove(key): 지정된 키와 연관된 값을 제거합니다.
  4. containsKey(key): 특정 키가 Map에 존재하는지 여부를 확인합니다.
  5. containsValue(value): 특정 값이 Map 내에 하나 이상의 키에 의해 매핑되어 있는지 확인합니다.
  6. size(): Map에 저장된 키-값 쌍의 개수를 반환합니다.
  7. isEmpty(): Map이 비어있는지 여부를 반환합니다.
  8. keys(): 모든 키를 반환합니다.
  9. values(): 모든 값들을 반환합니다.
  10. clear(): Map 내의 모든 키-값 쌍을 제거하여 비웁니다.

 

✔️ 구현

hash table과 tree-based로 크게 2가지 방식으로 구현할 수 있다.

이번 포스팅에서는 hash table에 대해 알아보자!

 

💋 Hash Table

✔️ 개념

  • 배열과 해시 함수(hash function)을 사용해 map을 구현한 자료 구조
  • (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠르다. ⇒ O(1)

 

✔️ Hash function이란?

 

  • 입력된 키를 일정한 크기의 숫자로 매핑하는 함수
  • 가능한 서로 다른 키들에 대해 다른 해시 값을 생성한다.
  • 좋은 해시 함수는 해시 충돌을 최소화하고 데이터를 고르게 분산 시킬 수 있다. ⇒ 뒤에서 자세히 설명

 

 

  • Hash Function의 input: 저장할 값의 key
  • Hash Function의 output: Hash Table을 구현한 배열에서 해당 key, value를 저장할 인덱스

⇒ key를 Hash Function에 넣으면, 해당 키와 값을 저장할 배열의 인덱스를 반환한다.

 

✔️ 동작 방식

 

 

  • insert
    • 데이터를 저장하려는 키를 해시 함수에 적용하여 해시 값을 구한다. ⇒ 배열의 인덱스로 사용
    • 계산된 해시 값에 해당하는 인덱스에 데이터를 저장한다.
      • key, hash (삽입 당시에 계산한 해시값), value의 3가지 값이 저장된다.
        • hash값은, 다시 해시 함수를 돌려서 계산하면 비효율적이어서 그냥 같이 저장한다고 한다.
  • get
    • 해시 함수를 사용하여 키의 해시 값을 계산해 인덱스로 이동해 저장된 데이터를 찾는다.

 

데이터를 저장할 인덱스를 버킷이나 슬롯이라고 부르기도 한다.

 

대략 아래와 같은 느낌으로 구현할 수 있다.

 

class HashTable:
	def __init__(self, size):
		self.size = size
		self.table = [None] * size

	def hash_function(self, key):
		return hash(key) % self.size

	def insert(self, key, value):
		index = self.hash_function(key)
		if self.table[index] is None:
			self.table[index] = [(key, value)]
		else:
			# Handle collision using chaining
			self.table[index].append((key, value))

	def get(self, key):
		index = self.hash_function(key)
		if self.table[index] is not None:
			# Search in the chain for the specified key
			for k, v in self.table[index]:
				if k == key:
					return v
		return None

 

💋 Hash Collision

✔️ 개념

해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 상황(key는 다른데, hash가 같을 때)이다.

해시 테이블의 크기는 제한되어 있기 때문에 현실적으로는 피할 수 없는 현상이다.

 

 

 

⇒ hash 충돌은 피할 수 없지만, 해시 함수의 결과 값이 골고루 분포되도록, 해시 충돌이 균등하게 발생하도록 해시 함수를 정하는 것이 좋다.

⇒ hash 충돌이 일어났을 때, 가장 효율적인 알고리즘을 통해서 충돌을 잘 해결하는 것이 중요하다!

 

✔️ hash collision의 해결 방법 - seperate chaining (체이닝)

  • 개념
    • 각 배열의 인덱스에 LinkedList를 사용하여 키들을 모아둔다.
    • 충돌이 발생하면 연결 리스트에 노드를 추가한다.

 

해시 테이블:
----------------------------
0:  -> [Data1] -> [Data4] -> ...
1:  -> [Data2] -> ...
2:  -> [Data3] -> ...
3: 
4: 
5:  -> [Data5] -> ...
6: 
7:  -> [Data6] -> ...
8: 
9: 
----------------------------

 

  • 과정
    1. 해시 테이블 초기화
      • 해시 테이블을 만들고, 각 인덱스에 빈 LinkedList를 할당한다.
    2. 데이터 삽입
      • 해당 데이터의 해시 값을 계산하고 그 해시 값을 인덱스로 하는 LinkedList에 데이터를 추가한다.
      • 해당 인덱스에 다른 데이터가 이미 존재하는 경우에, 그냥 LinkedList의 다음 노드에 데이터를 추가한다.
    3. 데이터 검색 또는 삭제
      • 동일한 해시 함수로 해당 인덱스을 찾고, LinkedList에서 데이터를 검색하거나 삭제한다.
  • 장점
    • 구현이 간단하고 유연하다.
    • 동적으로 크기를 조절하기 쉽다.
  • 단점
    • 메모리 사용이 비효율적일 수 있다. ⇒ 모든 인덱스에 LinkedList를 넣어놔야만 한다.
    • 연결 리스트의 길이가 길어지면 검색 시간이 길어질 수 있다. ⇒ LinkedList의 탐색 시간 복잡도는 O(n)
      • 참고: LinkedList 대신 트리를 사용하여 충돌을 해결할 수 있으며, 이로써 탐색 시간을 효율적으로 유지할 수 있다.

 

✔️ hash collision의 해결 방법 - open addressing (개방 주소법)

  • 개념
    • 충돌이 발생하면 다른 빈 버킷을 찾아 이동하거나 특정 규칙에 따라 다른 위치에 값을 저장한다.
      • 해시 값을 통해 나온 인덱스가 아닌, 다른 인덱스에 데이터를 저장한다!
      • 결국 하나의 인덱스에는 하나의 데이터만 저장된다.
    • 대표적인 개방 주소법에는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다.
  • 과정
    1. 해시 테이블 초기화
      • 해시 테이블을 만들고, 모든 버킷을 초기화한다.
    2. 데이터 삽입
      • 데이터를 삽입할 때, 해당 버킷이 비어있으면 데이터를 삽입
      • 충돌이 발생하면 다른 방법을 사용하여 빈 버킷을 찾아 데이터를 삽입
    3. 데이터 검색 또는 삭제
      • 검색 또는 삭제 시에도 동일한 방법으로 데이터를 찾거나 삭제
  • 장점
    • 메모리 사용이 효율적이다. ⇒ 인덱스에 직접 데이터를 저장하므로 오버헤드(포인터를 저장해야한다던가,,,)가 없다!
    • 캐시 효율이 높을 수 있다. ⇒ 데이터가 메모리에 연속적으로 저장되어 있어 캐시 라인(cache line) 활용이 쉽다!
  • 단점
    • 구현이 복잡할 수 있다. ⇒ 충돌 발생 시 어떤 인덱스에 데이터를 저장해야 할지 규칙을 정하기 어렵다.
    • 선형 탐사 방식에는 특정 영역에 데이터가 몰리는 클러스터링(Clustering)이 발생해 성능 저하가 발생할 수 있다.

 

💋 Hash Table Resizing

데이터가 많이 차면, 해시 테이블의 크기를 늘려주어야 한다.

 

 

현재 8개의 버킷 중 6개가 차있다. 자바에서는 capacity의 3/4이 차게 되면 사이즈를 늘리게 된다.

 

 

  1. 현재 데이터 이동
    • 기존 해시 테이블의 데이터를 새로운 크기의 해시 테이블로 이동시킨다.
    • 이동할 때에는 각 데이터의 해시 값을 다시 계산하지 않고, 이미 저장된 해시 값을 사용한다.
      • 데이터를 해시 테이블에 넣고 나면, 그 다음에는 해시 함수를 또 굴려서 해시값을 얻어내는게 아니라, 해시값을 위의 96, 202처럼 함께 저장한다.
  2. 새로운 해시 함수 사용
    • 해시 테이블이 리사이징되면, 해시 함수의 결과가 이전과 다를 수 있다.
    • 해시 테이블이 리사이징될 때는 새로운 해시 함수를 사용하여 데이터를 저장한다.
      • 위의 경우에, 기존에는 해시 값을 8로 나눈 나머지를 인덱스로 활용하다가, 해시 테이블의 크기를 늘리면서 해시값을 16으로 나눈 나머지를 인덱스로 사용하게 되었다.
  3. 크기 조절
    • 일반적으로 해시 테이블의 크기를 2배로 늘리는 경우가 많다.
      • 새로운 크기는 기존 크기의 2배인 소수(prime number)를 선택하는 것이 일반적이다.
      • 소수를 선택함으로써 해시 함수의 결과가 균등하게 분포되도록 할 수 있습니다.
  4. 재해시(Rehashing)
    • 해시 테이블의 크기가 변경되었으므로, 모든 데이터를 새로운 크기에 맞게 다시 해싱한다.
  5. 데이터 이동
    • 재해시된 결과를 기반으로 데이터를 새로운 크기의 해시 테이블에 이동시킨다.

 

💋 프로그래밍 언어 별 Hash Table 구현

 

✔️ Python

  • 파이썬에서는 내장된 dict 타입이 해시 테이블을 구현

 

pythonCopy code
# 해시 테이블 생성
my_dict = {}

# 데이터 추가
my_dict['key1'] = 'value1'

# 데이터 접근
print(my_dict['key1'])

 

✔️ Java

  • 자바에서는 HashMap 클래스를 사용해서 해시 테이블을 구현

 

javaCopy code
// 해시 맵 생성
HashMap<String, String> myMap = new HashMap<>();

// 데이터 추가
myMap.put("key1", "value1");

// 데이터 접근
System.out.println(myMap.get("key1"));

 

✔️ C++

  • C++에서는 std::unordered_map이 해시 테이블 구현

 

cppCopy code
// 해시 맵 생성
std::unordered_map<std::string, std::string> myMap;

// 데이터 추가
myMap["key1"] = "value1";

// 데이터 접근
std::cout << myMap["key1"] << std::endl;

 

✔️ JavaScript

  • 자바스크립트에서는 객체(Object)가 해시 테이블의 역할을 하고, Map 객체도 사용

 

javascriptCopy code
// 객체 생성
let myObj = {};

// 데이터 추가
myObj['key1'] = 'value1';

// 데이터 접근
console.log(myObj['key1']);

 

 

 

python은 dictionary의 유효 데이터 수 x 3와 같거나 큰 수 중에서 가장 작은 2의 배수를 새로운 capacity 크기로 결정한다. (python 3.10.x 기준)

 

💋 참고자료

  • https://www.geeksforgeeks.org/what-is-hashing/
  • https://www.baeldung.com/cs/hashing-separate-chaining
  • https://www.youtube.com/watch?v=ZBu_slSH5Sk&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=6
  • https://www.youtube.com/watch?v=HraOg7W3VAM

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!

 

반응형

'Computer Science > Data Structure' 카테고리의 다른 글

[자료구조] Graph: 개념, Vertices/Edges, 종류, 트리구조와 비교, 표현 (Adjacency Matrix vs Adjacency List)  (4) 2023.12.20
[자료구조] Set과 HashSet: 개념, List vs Set (메모리와 iteration 속도 관점에서)  (0) 2023.12.20
[자료구조] B-Tree 자료구조가 DB 인덱스에 사용되는 이유: secondary storage 접근과 block 단위의 저장 공간 활용 관점에서  (0) 2023.12.19
[자료구조] B-Tree의 개념, 파라미터, 데이터 삽입, 삭제 과정을 알아보자!  (2) 2023.12.18
[자료구조] AVL 트리의 개념, Balance Factor, 시간 복잡도와 한계에 대해 알아보자!  (0) 2023.12.17
  1. 💋 Map ADT
  2. ✔️ 개념
  3. ✔️ 주요 동작
  4. ✔️ 구현
  5. 💋 Hash Table
  6. ✔️ 개념
  7. ✔️ Hash function이란?
  8. ✔️ 동작 방식
  9. 💋 Hash Collision
  10. ✔️ 개념
  11. ✔️ hash collision의 해결 방법 - seperate chaining (체이닝)
  12. ✔️ hash collision의 해결 방법 - open addressing (개방 주소법)
  13. 💋 Hash Table Resizing
  14. 💋 프로그래밍 언어 별 Hash Table 구현
  15. ✔️ Python
  16. ✔️ Java
  17. ✔️ C++
  18. ✔️ JavaScript
  19. 💋 참고자료
'Computer Science/Data Structure' 카테고리의 다른 글
  • [자료구조] Graph: 개념, Vertices/Edges, 종류, 트리구조와 비교, 표현 (Adjacency Matrix vs Adjacency List)
  • [자료구조] Set과 HashSet: 개념, List vs Set (메모리와 iteration 속도 관점에서)
  • [자료구조] B-Tree 자료구조가 DB 인덱스에 사용되는 이유: secondary storage 접근과 block 단위의 저장 공간 활용 관점에서
  • [자료구조] B-Tree의 개념, 파라미터, 데이터 삽입, 삭제 과정을 알아보자!
깃짱
깃짱
연새데학교 컴퓨터과학과 & 우아한테크코스 5기 백엔드 스타라이토 깃짱
반응형
깃짱
깃짱코딩
깃짱
전체
오늘
어제
  • 분류 전체보기
    • About. 깃짱
    • Weekly Momentum
      • 2024
    • PROJECT
      • AIGOYA LABS
      • Stamp Crush
      • Sunny Braille
    • 우아한테크코스5기
    • 회고+후기
    • Computer Science
      • Operating System
      • Computer Architecture
      • Network
      • Data Structure
      • Database
      • Algorithm
      • Automata
      • Data Privacy
      • Graphics
      • ETC
    • WEB
      • HTTP
      • Application
    • C, C++
    • JAVA
    • Spring
      • JPA
      • MVC
    • AI
    • MySQL
    • PostgreSQL
    • DevOps
      • AWS
      • 아키텍처
    • frontend
      • HTML+CSS
    • NextJS
    • TEST
    • Industrial Engineering
    • Soft Skill
    • TIL
      • 2023
      • 2024
    • Linux
    • Git
    • IntelliJ
    • ETC
      • 日本語

블로그 메뉴

  • 홈
  • 깃허브

인기 글

최근 글

태그

  • 스트림
  • 예외
  • 람다
  • 우테코5기
  • 함수형프로그래밍
  • 람다와스트림
  • TDD
  • 우아한테크코스
  • OOP
  • 상속과조합
  • 컴포지션
  • 레벨로그
  • 우테코
  • 우아한테크코스5기
  • 상속
  • lamda
  • Java
  • Composition
  • 조합
  • Stream
hELLO · Designed By 정상우.v4.2.0
깃짱
[자료구조] Map과 Hash Table: 해시 함수와 해시 충돌의 해결, 해시 테이블 리사이징
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.