# 해시법

### 해시법

해시법 : '데이터를 저장할 위치' (= 인덱스) 를 간단한 연산으로 구하는 것을 말한다.

| **키**        | **5** | **6** | **14** | **20** | **29** | **34** | **37** | **51** | **69** |
| ------------ | ----- | ----- | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
| 해시값 (키 % 13) | 5     | 6     | 1      | 7      | 3      | 8      | 11     | 12     | 4      |

여기서 각각의 키를 13으로 나눈 값이 인덱스가 된다.

키를 해시값으로 변환하는 과정을 **해시 함수**라 하고,\
해시 테이블에서 만들어진 인덱스를 **버킷**이라고 한다.

해시 테이블을 크게 만들면 충돌 발생 없지만 메모리 낭비 + 느리다.\
해시 테이블 작게 만들면 충돌 발생하지만 검색, 추가, 삭제할 때 빠르다.

### 해시 충돌

위에 있는 해시 테이블에 18 넣으면 18 % 13 == 5 이므로 인덱스가 5가 되어야 한다.\
하지만 인덱스 5는 자리가 이미 차 있다.

이렇게 인덱스가 중복되는 것을 **해시 충돌**이라 한다.

> 해시충돌 대처법
>
> * 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.
> * 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

### 체인법

<figure><img src="/files/xZw7EiAtQNuTZEtX8RLd" alt=""><figcaption></figcaption></figure>

체인법에서는 중복값 나오면 노드로 연결해서 따로 뺀다.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/undefined-6.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.