Home Study | 자료구조 해시
Post
Cancel

Study | 자료구조 해시

자료구조 해시

목차

  1. 해시
  2. 해시 함수
  3. 해시 테이블


1. 해시

: 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑
해시 함수에 의해 얻어지는 값을 해시코드, 해시라고 함

2. 해시 함수

: key를 고정된 길이의 hash로 변경해주는 역할을 하여 이 과정을 hashing라고 함

  1. 해시충돌 : 서로 다른 key가 hashing 후 같은 hash값이 나오는 경우(발생확률이 적을수록 좋음)
    + 균등하게 발생하도록 하는 것도 중요함(모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해져서 좋지 않음)

  2. 좋은 해시함수의 조건
    특정 값에 치우치지 않고 해시값을 고르게 만들어내는 해시함수가 좋은 해시함수
    1. 충돌이 적어야함
    2. 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 함
    3. 계산이 빨라야 함

3. 해시 테이블

: 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조(= key-value로 이루어진 자료구조)

hash

  1. 해시 테이블의 구성

    • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
      (특정 조건에 맞춰 배열을 모두 순회할 필요가 없다는 소리)
    • 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼낼 수 있음
    • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
    • 해쉬 테이블의 길이(슬롯의 개수)를 늘리는 방법
    • 단, 파이썬에서는 해쉬를 별도로 구현할 이유가 없음 (딕셔너리 타입 { ‘key’: ‘value’ } 을 제공하기 때문)
    • JS 또한 별도로 구현할 필요가 없다 (객체 타입 { key: ‘value’ } 을 제공하기 때문)

  2. 해시 테이블의 장단점

    • 장점

      • 데이터 저장/읽기 속도가 빠름 (검색 속도가 빠름)
      • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
      • 해쉬는 키를 바탕으로 한 데이터의 여부(유무)를 파악하기 쉬움
    • 단점

      • 일반적으로 저장공간이 좀 더 많이 필요
      • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요
      • 해시 함수를 통해 나눠져 저장되는 해쉬 테이블의 주소가 같은데, 별도의 처리를 하지 않을 경우 : 키를 바탕으로 한 데이터가 덮어씌워질 가능성이 있음
      • 중복이 일어나지 않도록 해쉬 테이블의 공간을 넓게 설계해야 함

  3. 주요 용도

    • 검색이 많이 필요한 경우
    • 저장, 삭제, 읽기가 빈번한 경우
    • 캐쉬 구현시 (중복 확인이 쉽기 때문)






출처

해시
해시 테이블
해시 테이블과 해시함수
좋은 해시함수

This post is licensed under CC BY 4.0 by the author.