---

해시 테이블(Hash Table)

해시 테이블은 키-값 쌍을 저장하며, 키를 통한 데이터 접근이 빠른 자료 구조입니다.

Keywords: #해시테이블 #자료구조 #키값

---

해시 테이블의 정의

• 키(Key)와 값(Value): 데이터는 키와 값을 갖고, 키는 중복될 수 없습니다.
• 해시 함수(Hash Function): 키를 입력 받아 해시값을 반환합니다.
• 충돌(Collision): 다른 키가 같은 해시값을 가질 때 발생합니다.
  1. 제한된 배열 크기 : 해시테이블의 크기는 일반적으로 제한되어 있기 때문에 이로 인해 다양한 키가 한정 된 수의 인덱스에 매핑되어야 하므로 충돌이 발생할 확률이 높아짐
  2. 비균등한 해시 함수 :해시 함수가 키를 균등하게 분포시키지 못할 경우, 특정 인덱스에 값이 집중되어 충돌이 자주 발생할 수 있음
  3. 키의 유사성 : 만약 입력 키가 특정 패턴을 가지고 있다며느, 그 패턴에 따라 해시 값도 유사한 패턴을 가질 수 잇어 충돌이 발생할 확률이 높아짐
  4. 부족한 해시함수 : 해시 함수가 단순하거나 복잡도가 낮을 경우, 다양한 키에 대해 다양한 해시 값을 생성하지 못하므로 충돌이 더 자주 발생할 수 있음.
• 빠른 검색 속도: 키를 이용해 빠른 데이터 접근이 가능합니다.

---

해시 테이블의 사용 사례

1. 데이터베이스: 키-값 검색 및 저장
2. 캐시: 최근 사용된 항목의 빠른 검색 및 저장
3. 빠른 데이터 조회: 키를 통한 빠른 데이터 접근이 필요한 경우

---

해시 테이블의 구현

배열과 해시 함수를 사용하여 구현. 충돌 시, 연결 리스트나 오픈 어드레싱 등으로 해결.

---

해시 테이블 초기화

파이썬:

hash_table = {}

C:

#include <stdio.h>
#define TABLE_SIZE 100

typedef struct {
    char* key;
    char* value;
} HashEntry;

HashEntry hashTable[TABLE_SIZE];

---

삽입 연산

파이썬:

def insert(key, value):
    hash_table[key] = value

C:

void insert(char* key, char* value) {
    int hashValue = hashFunction(key);
    hashTable[hashValue].key = key;
    hashTable[hashValue].value = value;
}

---

조회 연산

파이썬:

def get(key):
    return hash_table.get(key, "Key not found!")

C:

char* get(char* key) {
    int hashValue = hashFunction(key);
    if (hashTable[hashValue].key == NULL) {
        return "Key not found!";
    }
    return hashTable[hashValue].value;
}

---

삭제 연산

파이썬:

def delete(key):
    if key in hash_table:
        del hash_table[key]
    else:
        print("Key not found!")

C:

void delete(char* key) {
    int hashValue = hashFunction(key);
    if (hashTable[hashValue].key == NULL) {
        printf("Key not found!\n");
        return;
    }
    hashTable[hashValue].key = NULL;
    hashTable[hashValue].value = NULL;
}

---

해시 테이블의 주된 장점은 키를 통한 빠른 접근이 가능하지만, 충돌과 해시 함수의 선택에 따라 성능이 영향을 받을 수 있습니다.

---