[자료구조] 해시, 해시맵

2022. 8. 6. 13:39학습/CS

반응형

자료구조 해시맵

0. 해시가 나온 상황

배열의 경우 내부 인덱스를 통해서 자료의 검색을 한번에 함

  • 장점: 빠른 검색
  • 단점: 데이터의 삽입, 삭제 시 많은 데이터가 이동하게됨 (시간 소요!)

 

연결리스트는 해당 노드를 검색하기위해 순회 검색을 함

  • 장점: 데이터의 삽입, 삭제 시 인근노드들의 참조 값만 수정하면 됨
  • 단점: 느린 검색

 

이 과정에서 해쉬라는 데이터를 다루는 방법이 나오게 됨

 


1. 해시 원리

해시함수F(key) => HashCode => 배열의 index => index와 value가 한쌍으로 존재하게 됨
  1. key가 해시함수를 거쳐서 HashCode로 바뀌게되고
  2. HashCode가 배열의 크기에 맞는 Index 로 변환이 됨
  3. 해당 Indexvalue를 할당하여 (key, value) 형태의 테이블을 형성하게 됨
  • key 값이 크든 말든 동일한 HashCode를 만들어줌
    • 데이터를 해시코드로 바꾸는 해시함수(해시알고리즘)는 개발자에 따라 다름
  • HashCode는 무수한 수로 나올 수 있지만 배열의 크기는 한계가 있음
    • 해시코드를 배열의 크기로 나누고 나머지를 Index로 사용함
    • 그렇다면 같은 인덱스가 나올수 있겠지?
      • 이를 해시충돌이라고함

해시충돌

  • 이 충돌을 해결하는 방법은 두가지
    • open addressing - 겹치면 비어있는 인근 인덱스로 넘기는 방법
    • Separate Chaining - 해당 인덱스에서 링크드리스트로 엮음
    • 데이터가 적은경우 open addressing 가 효율이 좋을것이라는게 예상될 것이고 실제로도 그렇다

 


2. 특징

빠른탐색

  • 유일한 값을 통해서 원소에 접근하는데 유용하게 쓰임
  • 대부분의 시간복잡도가 O(1)
    • 알고리즘 풀이 시 원소를 넣거나 삭제, 찾는 일이 많을 때에는 해시를 사용하는 것이 좋음

 

추가적으로 키에 대한 데이터의 유무와 중복 확인이 쉬움

 


3. 활용 - 파이썬

파이썬에서는 Dictionary 라는 자료구조를 통해 해시를 제공합니다.

용도

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

 


4. Etc

해시맵과 해시테이블의 차이?

두개 다 key, value를 가진 map 자료구조이다.

  • 중복키에 대한 처리
    • 해시 테이블은 키가 값은 같은 값을 두번 넣으면 초기값을 유지함
    • 해시맵은 키가 값은 같은 값을 두번 넣으면 두번째 값으로 덮어버림
  • Null값
    • 해시맵은 키에 Null값을 허용한다.

  • key 와 Value를 갖는 자료구조이다.
  • 효율적인 검색을 위해서 사용된다.

 


참조

  • 해시 전반적인 내용
 

[자료구조] 해시 Hash, 해시맵 HashMap

1. 해쉬는 왜 생겼지? 가장 기본적인 자료구조인 배열의 경우 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이

selina-park.tistory.com

  • 해시맵과 해시 테이블의 차이, 해시 충돌
 

자바 해시 테이블( Hashtable), 해시 맵(HashMap) 구조와 원리

막연하게 자바 해쉬 테이블이나 해쉬 맵을 당연하게 사용하고 있었다. 이를 테면 자전거를 타는 방법은 아는데 남한테 설명을 하라고 하면 제대로 설명을 하지 못하는 것과 비슷한 느낌이다. 예

nhj12311.tistory.com

 

반응형