해시테이블에 대해서 설명해 주세요.

[dailynj]

[dailynj]

해시 테이블이란 key, value 로 데이터를 저장하고 값을 꺼낼때는 key 값을 이용해 고유한 index 를 생성하고 그 index 에 저장된 값을 꺼내오는 자료구조입니다. 해시 테이블의 시간복잡도는 충돌이 일어나지 않을경우 O(1) 로 빠르게 데이터를 검색할 수 있다는 특징이 있습니다.

해시함수는 임의의 길이의 데이터를 고정된 길이의 값으로 변경하고 고유한 인덱스를 계산하는 함수로 Division Method, Digit Folding, Multiplication Method, Universal Hashing 등의 방법이 있습니다. 만약 해시값이 충돌하게 된다면 Seperating Chaining이나 open address 방식으로 해결할수 있습니다. seperating chaining 방식은 같은 인덱스를 가지는 값들을 연결리스트로 이어붙이는 방식입니다. 이는 최악의 상황에 O(N) 의 시간복잡도를 가질 수 있다는 단점이 있습니다. Open address 방식은 총 3가지로 linear, quadratic, double hashing 방식이 있습니다. linear 는 현재 버킷의 index 부분에 자리가 차 있으면 고정폭만큼 조금씩 이동하여 빈공간이 나오면 그 공간에 저장하는 방식이고 qudratic 은 해시 저장순서의 폭은 1^2, 2^2, 3^2 만큼 이동하면서 빈공간에 넣는 방식이고 이 둘 모두 clustering 문제가 발생할 수 있어서 이를 해결하기 위한 double hashing 방식이 있습니다. double hashing 방식은 두개의 서로다른 계산법을 통해 하나의 함수로 이동했을 때 그 칸이 차있으면 다른 함수로 또 이동하게 되어 중복된 값이 최대한 나오지 않도록 하는 방법입니다.

그럼에도 hash function 의 충돌을 해결하기 위한 가장 좋은 방법은 메모리의 크기를 늘리는것이 우선이고 다음으로는 중복된 데이터가 최대한 들어오지 않도록 하는 것입니다. 만약 중복된 데이터가 자주 들어오는 경우라면 hash table이 아닌 다른 자료구조를 사용하는 것도 하나의 방법입니다.

[co3oing]

해시테이블이란 키와 값으로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다는 특징이 있습니다.

해시테이블이 빠른 검색속도를 제공할 수 있는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문입니다. 각각의 키에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색합니다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬록이라고 합니다.
해시 함수를 1번만 수행해 데이터를 저장, 삭제, 조회하기 때문에 평균 시간복잡도는 O(1)이됩니다. 하지만 이 해시 함수를 돌려 나온 index가 동일하다면 해시가 충돌하게 됩니다. 이런 경우에는 연결된 리스트까지 검색해야 하므로 O(N)까지 시간복잡도가 증가할 수 있습니다.

[duyeonnn]

HashTable

해시 테이블은 (key, value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 key 값에 해시함수를 적용해 배열의 고유한 Index를 생성하고 이 index 값을 활용해 값을 저장하거나 검색하게 된다.

Hash Function

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 대표적인 해시 함수로는 아래의 3가지가 있다.

1. Divisiton Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법
3. Multiplication Method: 숫자로 된 key값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용해 다음과 같은 계산을 한다. h(k) = (kAmod1) x m
4. Univeral hashing: 다수의 해시함수를 만들어 집함 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법

Hash 값이 충돌하는 경우

다른 key값에 대해 hash값이 동일한 값이 나오는 경우가 생길 수 있다. 이런 경우를 충돌이라 하고 충돌에 의한 문제를 해시테이블에서는 크게 분리 연결법과 개방 주소법 2가지 방법으로 해결하고 있다.

[분리 연결법]

분리 연결법은 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 이러한 방식은 해시 테이블의 확장이 필요 없고 간단하게 구현이 가능하며 손쉽게 삭제할 수 있다는 장점이 있지만 동일한 버킷에 체이닝되는 데이터가 많아지면 효율성이 감소한다는 단점이 있다.

[개방 주소법]

추가적인 메모리를 사용하는 체이닝 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. 대표적으로 아래와 같은 3가지 방식이 존재한다.

1. Linear Probing: 현재의 버킷 index로 부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장한다.
2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식. 예를 들어 처음 충돌이 발생한 경우 1만큼 이동하고 그 다음 계속 충돌이 발생하면 4, 9 칸씩 옮기는 방식
3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

개방 주소법에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다.

[inuinseoul]

Key-Value를 기반으로 데이터를 저장하는 자료구조입니다. 해시테이블은 Key값에 해시함수를 적용해 고유한 자연수값을 생성할 수 있습니다.

해시함수는 특정값을 특정범위의 자연수로 변경해주는 함수입니다. 해시함수는 결정론적이어야하며, 각 범위의 자연수들의 리턴확률이 비슷해야하고, 빨리 계산할 수 있어야합니다. 대표적으로 3가지가 존재합니다. 물론 이들을 섞어 사용할 수도 있습니다.

• Division Method : 입력값을 테이블의 크기로 나누고 그 나머지를 주소로 사용하는 것
• Digit Folding : Key의 문자열을 아스키코드로 바꾸고 그를 합한 데이터를 테이블 주소로 사용하는 것
• Multiplication Method : 0 < a < 1인 아무값을 Key에 곱한 다음, 그 결과값에 배열의 크기를 곱해 테이블 주소로 사용하는 것

해시함수를 통해 생성된 값이 겹쳐 해시값이 충돌되는 경우에는 링크드리스트를 활용해 값을 추가저장하는 Data Chaining을 사용하거나 다른 비어있는 주소에 값을 넣어주는 Open Addressing을 사용해 해결할 수 있습니다.

[sustainable-git]

HashTable은 key, value로 data를 저장하는 자료구조로 빠르게 data를 검색할 수 있습니다. 각각의 key값에 hash함수를 적용해 고유한 index를 생성하고 이 index를 활용해 값을 저장하거나 검색합니다. hash값이 충돌하여 중복된 index value가 나오는 경우가 있는데, 이럴 때에는 분리 연결법 또는 개방 주소법을 이용해 문제를 해결합니다.

• 개방주소법

  • 충돌이 발생하면 table 내 새로운 주소를 탐사한 후 비어있는 곳에 data를 입력하는 방식

• 분리연결법

  • Hash Table에 Node 객체를 저장해 충돌이 발생하는 data는 다음 Node에서 찾는 방식