728x90

해시 (Hash)

Data Structure 네 번째 스터디 : 해시 (Hash)

해시(Hash)란?

해시(Hash, Hash Code) : 다양한 길이의 데이터를 고정된 길이의 데이터로 매핑한 값
해시 함수(Hash Function): 임의의 길이의 데이터를 고정된 길이의 데이터(해시, Hash)로 매핑하는 함수
- 가장 널리 사용되는 해시함수에는 MD5와 SHA-1 등이 있음
- MD5: 무결성 검사 등에 사용되는 128비트 암호화 해시 함수
- SHA-1: 미국 국가안보국이 설계한 160비트 해시값을 만드는 암호화 해시 함수로 미국의 연방 정보 처리 표준
해시 테이블(Hash Table): 키와 같을 매핑해둔 데이터 구조
- 해시 함수로 얻은 해시를 키(index)로 사용
- 내부적으로 배열을 사용해 index에 따라서 데이터를 저장
- 효율적인 검색
- 동기화를 지원
- key나 value에 NULL 값을 허용하지 않음
- 데이터가 많아지면 충돌이 발생할 수도 있음 → 해결 필요

Open Addressing Method : 해시 함수로 얻은 주소가 아닌 다른 주소 사용
- Linear Probing (선형 조사): 충돌 발생 시 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 대신 저장
  - 장) 계산이 단순
  - 단) 검색에 시간이 많이 소요되고, 테이블 내에 데이터들이 일정한 키값으로 모이는 현상 발생
- Quadratic Probing (이차 조사): 선형 조사법이 n칸 옆을 검사한다면, 이차 조사법은 n^2^ 칸 옆 검사
  - 장) Linear Probing의 일정한 키값으로 모이는 현상 해소
  - 단) 모든 공간을 다 검사하지는 않음
- Double Hash (이중 해시): 충돌이 발생하면 두 번째 해시함수를 사용하여 해시값을 가지도록 함
- Rehasing (재해싱): 해시 테이블의 크기를 늘리고 새로운 해시 테이블의 크기에 맞추어 모든 데이터를 다시 해싱. 단, 상당히 많은 비용 발생
Closed Addressing Method : 해시 함수로 얻은 주소 사용
- Chaining (체이닝): 해시 테이블 자체는 포인터 배열로 만들고, 같은 인덱스(버켓)에 해당하는 데이터들을 체인형식(Linked List)으로 만들어 연결
  - 장) 삽입과 삭제가 용이함
  - 단) 따로 동적인 공간을 할당해야 함, 검색 시 선형 탐색으로 인해 속도가 느림 O(N)

Hash Table: 자바에서 해시 테이블을 구현한 클래스 중 가장 오래된 것. 컬렉션 프레임워크가 만들어지기 이전부터 존재하던 것이기 때문에, 컬렉션 프레임워크의 명명법을 따르지 않음 (가능한 사용 지양)
Hash Map: 자바에서 해시 테이블을 구현한 것 중 두 번째 클래스. Map 인터페이스를 구현하기 위해 Hash Table을 사용하였음

728x90

[Data Structure] 맵(Map) \| 맵이란? \| HashMap \| TreeMap \| LinkedHashMap (0)	2022.04.13
[Data Structure] 트라이(Trei) \| 트라이란? \| 트라이의 구조 \| 트라이의 특징 (0)	2022.04.13
[Data Structure] 이진 탐색 트리 \| BST \| Binary Search Tree \| 시간복잡도 \| 전위/중위/후위 순회 (0)	2022.04.05
[Data Structure] B Tree(Balanced Tree) \| B Tree 규칙 \| B+ Tree \| B Tree와 B+ Tree 차이 (0)	2022.03.29
[Data Structure] Heap(힙) 자료구조 \| 우선순위 큐(Priority Queue) \| Heapify (0)	2022.03.29