12/26 1조 조별발표 - 해시(hash)

Leafy·2023년 12월 26일

중앙_자바

목록 보기

17/76

해시(hash)란?
수학적 함수(mathematical function)를 이용해 어떤 길이의 입력값이라도(input of any length) 고정된 길이의 문자열(fixed size string of text)로 processing 하는 것.

윤성우의 열혈 자료구조 책 참고👇

자료구조의 테이블

자료구조 관점에서는 아무 표나 테이블이라고 하지 않음.
저장되는 데이터가 key와 value의 쌍으로 이루어졌을 때를 table이라고 한다.
테이블에 저장되는 모든 데이터들은 이를 구분하는 key가 있어야 하고,
이 key는 데이터를 구분하는 기준이 되므로 중복이 되어서는 안 됨.

key가 존재하지 않는 value는 저장할 수 없다. 그리고 모든 key는 중복되지 않음.

이런 테이블 자료구조의 예시
아파트 우편함. '호수'가 key, '우편물'이 value.
여기서 '단번에' 우편물을 찾을 수 있는데, 이건 시간복잡도가 O(1)이라는 뜻이다.
https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o#chaining-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84big-o
다른 테이블 예시
사전(dictionary).
사전은 단번에 못 찾는데? 양이 많아서 여러 페이지에 담겨 있으니까 그런 것.
펼친 페이지에서 원하는 값은 단번에 찾을 수 있다.
모든 내용을 한 페이지에 적어뒀다고 치면 한번에 찾을 수 있다.
단어 자체가 key, 그것에 대한 설명이 value.
표의 형태를 취하지 않더라도 편집 상태의 문제일 뿐, 자료구조의 관점에서는 편집 상태는 상관이 없다.

자료 구조의 Table = Dictionary(사전 구조) = Map(맵)
이라 불리기도 한다.

좋은 해시 함수

메모리에서 데이터가 테이블의 전체 영역에 고르게 분포된 것.
= 그만큼 충돌이 발생할 확률이 낮다는 것.
충돌은 피해야할 것이 아니라 해결해야하는 것.
충돌의 해결책이 마련돼 있다고 하더라도 충돌이 덜 발생해야 데이터의 저장, 삭제 및 탐색의 효율을 높일 수 있음.

좋은 해시 함수는 충돌을 덜 일으키는 해시 함수.

좋은 해시 함수 디자인 방법? 정답은 없다.
상황에 따라, 즉 key의 특성에 따라 달라짐.

하지만 일반적인 조언은 있다.

좋은 해시 함수는 키의 일부분을 참조하여 해시 값을 만들지 않고, 키 전체를 참조하여 해시 값을 만들어낸다.

자릿수 선택(Digit Selection) 방법과 자릿수 폴딩(Digit Folding) 방법

key 전체를 참조하는 방법과 관련한 다양한 해시 함수 디자인 방법 중 하나

자릿수 선택(Digit Selection)
여덟 자리의 수로 이뤄진 key에서 다양한 해시 값 생성에 도움을 주는 네 자리의 수를 뽑아서 해시 값을 생성한다.

key의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해시 값을 생성하는 지극히 상식적인 방법.
-> 유사한 방법으로 '비트 추출 방법'이라는 것이 있다. 탐색 key의 비트 열에서 일부를 추출 및 조합하는 방법

자릿수 폴딩(Digit Folding)
종이를 접듯이 숫자를 겹치게 해 더한 결과를 해시 값으로 결정하는 방법.
2 7 | 3 4 | 1 9
이렇게 접으면 27과 34와 19가 겹침.
겹친 두 자릿수 숫자를 모두 더하면 그 결과는 80이 되는데,
이를 해시 값이라 하면 이는 여섯 자리의 숫자를 모두 반영해 얻은 결과라 할 수 있다.

이외에도 key를 제곱해 그 중 일부를 추출하는 방법, 폴딩 과정에서 덧셈 대신 XOR 연산을 하는 방법, 둘 이상의 방법을 조합하는 방법 등 통계적으로 보다 넓은 분포를 보이는 다양한 방법들이 소개되고 있다.

해시 함수를 디자인할 때에는 이런 방법들보다 key의 특성이나 저장공간의 크기를 고려하는 것이 우선.

충돌(Collision)문제의 해결책

테이블의 핵심 주제라 할 수 있는 충돌 문제.
간단히 말하면 충돌이 발생한 그 자리를 대신해서 빈 자리를 찾는 것.
다만 빈 자리를 찾는 방법에 따라 해결책이 구분될 뿐.

열린 어드레싱(Open Addressing)

충돌이 발생하면 다른 자리에 대신 저장한다는 의미.

선형 조사법(Linear Probling)과 이차 조사법(Quadratic Probing)

선형 조사법(Linear Probling)
충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것.
key를 해싱했을 때 자리가 겹칠 경우 바로 옆 자리(인덱스 + 1, 인덱스 + 2, ...)로 이동해서 자리를 살피는 것.

문제점은 충돌 횟수가 증가하면
클러스터(cluster)현상 = 특정 영역에 데이터가 집중적으로 몰리는 현상
이 생긴다.
클러스터 현상은 충돌의 확률을 높이는 직접적인 원인이 됨.

이차 조사법(Quadratic Probing)
이 단점을 보완하기 위해 나온 것이 이차 조사법.
간단히 말하면 빈 공간을 바로 옆에서 찾지 말고 좀 멀리서 찾는 방법.
선형 조사법은 충돌 발생 시 n칸 옆의 슬롯을 검사한다면, 이차 조사법은 n^2칸 옆의 슬롯 검사.

이중 해시(Double Hash)

해시 값이 같으면 충돌 발생 시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다.

해시 값이 같을 경우, 빈 슬롯을 찾아서 접근하는 위치가 n^2으로 동일하기 때문에, 선형 조사법 보다는 낫지만 접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확률은 여전히 높음.

그 해결 방안은?

이중 해시(Double Hash)
2개의 해시 함수를 사용.
이차 조사법은 1칸, 4칸, 9칸... 식으로 규칙적으로 빈 공간을 찾으므로 이것을 불규칙적으로 구성하면 어떨까? <-에 착안한 방법.

1차 해시 함수: key를 근거로 저장위치 결정

2차 해시 함수: 충돌 발생 시 몇 칸 뒤를 살필지 결정

닫힌 어드레싱(Closed addressing)

앞서 소개한 Open Addressing 방법들과 다른 방법.
무슨 일이 있어도 자기 자리에 들어간다. 충돌이 발생해도 자기 자리.

자리를 여러 개 마련할 수밖에 없는데, 배열로 마련하는 것과 연결 리스트(Linked List)로 마련하는 것이 있다.

배열로 마련하는 방법은 2차원 배열을 구성해서 해시 값 별로 다수의 슬롯을 마련하는 것인데, 흔한 방법X
충돌이 발생하지 않을 경우 메모리 낭비가 심하고, 충돌의 최대 횟수를 결정해야 하는 부담이 존재.

체이닝(Chaining)

연결 리스트(Linked List)를 이용해 슬롯을 연결하는 방법. 닫힌 어드레싱 방법의 대표격.

탐색할 때는 같은 해시 값으로 묶여 있는 연결된 슬롯을 모두 조사해야 한다는 불편함이 있지만,

이는 해시 함수를 잘 정의해 충돌 확률이 높지 않다면 연결된 슬롯의 길이는 부담스러울 정도는 아니다.

(참고) Hashtable 해시 테이블

Array와 Linked List(dynamic을 얻고 O(n)으로 퇴보. 삽입은 편함.)를 조합한 것.
시간복잡도 O(1)을 달성! <- 열혈 자료구조 책에서도 이렇게 나옴.
binary search 하려고 linked list에서 pointer 2개씩 낀 binary search tree 구조(Array처럼 O(log n) 회복)를 만들었는데
그보다 더 효율적으로 바로바로 접근할 수 있음.

엄밀히 말하면 O(n)지만, O(1) 된다.
되게되게 많은 배열(buckets) 쓰거나 (공간)
엄청 괜찮은 충돌없는 해시 함수 찾는 데 공을 들이거나 (시간?)
여튼 둘 중 하나는 할 거니까 실제로는 O(n)보다 평균적으로 빠름.
모든 이름이 한 bucket에 들어가는 운 나쁜 경우,, 제외하면?

(참고) HashMap 해시맵

Bard 답변

해시맵은 왜 해시맵이야?

해시맵은 해시 테이블을 기반으로 한 자료 구조입니다. 해시 테이블은 해시 함수를 사용하여 데이터를 고정된 길이의 버킷에 저장합니다. 해시맵은 해시 테이블에 키와 값을 저장하는 방법을 제공합니다.

해시맵이 "맵"이라고 불리는 이유는 다음과 같습니다.

키와 값을 매핑합니다.
키를 사용하여 값을 빠르게 찾을 수 있습니다.
해시맵이 "해시"라고 불리는 이유는 다음과 같습니다.

해시 함수를 사용하여 데이터를 버킷에 저장합니다.
해시 함수를 사용하여 데이터를 빠르게 검색합니다.
즉, 해시맵은 키와 값을 매핑하는 데 해시 함수를 사용하는 자료 구조입니다. 따라서 "맵"과 "해시"라는 이름을 가지고 있습니다.

자세히 설명하면, 해시맵은 키와 값을 하나의 쌍으로 저장하는 자료 구조입니다. 키는 데이터를 식별하는 데 사용되는 값입니다. 값은 키와 관련된 데이터입니다.

해시맵은 해시 함수를 사용하여 키를 버킷에 저장합니다. 버킷은 키와 값이 저장되는 위치를 나타내는 정수입니다.

키를 사용하여 값을 검색하려면 먼저 키에 대한 해시 값을 계산합니다. 계산된 해시 값을 사용하여 데이터가 저장된 버킷을 찾습니다. 찾은 버킷에서 키와 일치하는 값을 찾습니다.

해시맵은 데이터 검색에 매우 효율적인 자료 구조입니다. 데이터의 개수가 많아지더라도 검색 시간을 효율적으로 유지할 수 있습니다.

해시맵은 다양한 분야에서 사용됩니다. 예를 들어, 다음과 같은 용도로 사용됩니다.

데이터베이스: 데이터베이스의 인덱스로 사용됩니다.
파일 시스템: 파일의 정보를 저장하는 데 사용됩니다.
웹 애플리케이션: 사용자 정보를 저장하는 데 사용됩니다.

해시맵의 원리를 설명해 줘

해시맵은 해시 테이블을 기반으로 한 자료 구조입니다. 해시 테이블은 해시 함수를 사용하여 데이터를 고정된 길이의 버킷에 저장합니다. 해시맵은 해시 테이블에 키와 값을 저장하는 방법을 제공합니다.

해시맵의 원리는 다음과 같습니다.

키와 값을 하나의 쌍으로 저장합니다.
해시 함수를 사용하여 키를 버킷에 저장합니다.
키를 사용하여 값을 검색합니다.
키와 값을 하나의 쌍으로 저장

해시맵은 키와 값을 하나의 쌍으로 저장합니다. 키는 데이터를 식별하는 데 사용되는 값입니다. 값은 키와 관련된 데이터입니다.

예를 들어, 다음과 같은 데이터를 해시맵에 저장할 수 있습니다.

키	값
"apple"	"사과"
"banana"	"바나나"
"cherry"	"체리"

이 경우 키는 "apple", "banana", "cherry"이고 값은 "사과", "바나나", "체리"입니다.

해시 함수를 사용하여 키를 버킷에 저장

해시맵은 해시 함수를 사용하여 키를 버킷에 저장합니다. 버킷은 키와 값이 저장되는 위치를 나타내는 정수입니다.

해시 함수는 키를 고정된 길이의 해시 값으로 변환합니다. 해시 값은 0에서 n-1 사이의 정수입니다. 여기서 n은 버킷의 개수입니다.

예를 들어, 다음과 같은 해시 함수가 있다고 가정합니다.

int hash(String value) {
int hash = 0;
for (char c : value.toCharArray()) {
hash = hash * 31 + c;
}
return hash % 10;
}
이 해시 함수는 문자열을 숫자로 변환합니다. 변환된 숫자는 0에서 9 사이의 정수입니다.

이 해시 함수를 사용하여 위의 데이터를 해시맵에 저장하면 다음과 같은 결과가 나옵니다.

버킷	키	값
0	apple	사과
1	banana	바나나
2	cherry	체리

"apple"의 해시 값은 13입니다. 13을 10으로 나눈 나머지는 3입니다. 따라서 "apple"은 버킷 3에 저장됩니다.

키를 사용하여 값을 검색

예를 들어, "apple"의 값을 검색하려면 다음과 같은 과정을 거칩니다.

"apple"에 대한 해시 값을 계산합니다.
계산된 해시 값인 13을 사용하여 데이터가 저장된 버킷을 찾습니다.
버킷 3에서 키가 "apple"인 데이터를 찾습니다.
이 과정을 통해 "apple"의 값인 "사과"를 찾을 수 있습니다.

해시맵은 데이터 검색에 매우 효율적인 자료 구조입니다. 데이터의 개수가 많아지더라도 검색 시간을 효율적으로 유지할 수 있습니다.

해시맵은 다양한 분야에서 사용됩니다. 예를 들어, 다음과 같은 용도로 사용됩니다.

데이터베이스: 데이터베이스의 인덱스로 사용됩니다.
파일 시스템: 파일의 정보를 저장하는 데 사용됩니다.
웹 애플리케이션: 사용자 정보를 저장하는 데 사용됩니다.
프로필 사진
해시에서 버킷이 뭐야?
해시에서 버킷은 데이터를 저장하는 공간입니다. 해시 테이블은 해시 함수를 사용하여 데이터를 고정된 길이의 버킷에 저장합니다.

해시 테이블은 다음과 같이 구성됩니다.

버킷	데이터
0	apple
1	banana
2	cherry

이 경우 버킷 0에는 키가 "apple"인 데이터가 저장되어 있습니다. 버킷 1에는 키가 "banana"인 데이터가 저장되어 있습니다. 버킷 2에는 키가 "cherry"인 데이터가 저장되어 있습니다.

해시 테이블은 해시 함수를 사용하여 데이터를 버킷에 저장합니다. 해시 함수는 데이터를 고정된 길이의 해시 값으로 변환합니다. 해시 값은 0에서 n-1 사이의 정수입니다. 여기서 n은 버킷의 개수입니다.

예를 들어, 다음과 같은 해시 함수가 있다고 가정합니다.

이 해시 함수를 사용하여 위의 데이터를 해시테이블에 저장하면 다음과 같은 결과가 나옵니다.

버킷	키	값
0	apple
1	banana
2	cherry

"apple"의 해시 값은 13입니다. 13을 10으로 나눈 나머지는 3입니다. 따라서 "apple"은 버킷 3에 저장됩니다.

해시 테이블은 데이터 검색에 매우 효율적인 자료 구조입니다. 데이터의 개수가 많아지더라도 검색 시간을 효율적으로 유지할 수 있습니다.

Java HashMap 작동원리

https://d2.naver.com/helloworld/831311

둘 모두 Worst Case O(M)이다. 하지만 Open Addressing은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비하여 캐시 효율이 높다. 따라서 데이터 개수가 충분히 적다면 Open Addressing이 Separate Chaining보다 더 성능이 좋다. 하지만 배열의 크기가 커질수록(M 값이 커질수록) 캐시 효율이라는 Open Addressing의 장점은 사라진다. 배열의 크기가 커지면, L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문이다.

Java HashMap에서 사용하는 방식은 Separate Chaining이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문

HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case 또는 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있다(여기에 대해서는 "보조 해시 함수"에서 설명하겠다).

보조 해시 함수(supplement hash function)

보조 해시 함수(supplement hash function)의 목적은 '키'의 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것

Leafy

0o0

다음 포스트