hash 자료형

 python 딕셔너리 자료형

사람은 누구든지 "이름" = "홍길동", "생일" = "몇 월 몇 일" 등으로 구분할 수 있다. 파이썬은 영리하게도 이러한 대응 관계를 나타낼 수 있는 자료형을 가지고 있다. 요즘 사용하는 대부분의 언어들도 이러한 대응 관계를 나타내는 자료형을 갖고 있는데, 이를 연관 배열(Associative array) 또는 해시(Hash)라고 한다.

파이썬에서는 이러한 자료형을 딕셔너리(Dictionary)라고 하는데, 단어 그대로 해석하면 사전이라는 뜻이다. 즉, people이라는 단어에 "사람", baseball이라는 단어에 "야구"라는 뜻이 부합되듯이 딕셔너리는 Key와 Value라는 것을 한 쌍으로 갖는 자료형이다. 예컨대 Key가 "baseball"이라면 Value는 "야구"가될 것이다.

딕셔너리는 리스트나 튜플처럼 순차적으로(sequential) 해당 요소값을 구하지 않고 Key를 통해 Value를 얻는다. 이것이 바로 딕셔너리의 가장 큰 특징이다. baseball이라는 단어의 뜻을 찾기 위해 사전의 내용을 순차적으로 모두 검색하는 것이 아니라 baseball이라는 단어가 있는 곳만 펼쳐 보는 것이다.

출처 https://wikidocs.net/16

규모가 큰 데이터를 비교해야할 때 list 형태로 순차적으로 비교하는 것은 시간이 O(n2) 걸리게 된다. 

이때 hash 를 사용하게 되면 시간을 절약할 수 있다. 

Hash 란

해쉬란 임이의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다. 이를 이용해 특정한 배열의 인덱스나 위치, 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던 것에 비해, 해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.

1. Direct Addressing Table

Direct Addressing Table은 key-value 쌍의 데이터를 배열에 저장할 key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.

예를 들면 400인 데이터가 있다면 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다. 똑같은 키 값이 존재하지 않는다고 가정하면 삽입 시에는 각 키마다 자신의 공간이 존재하므로 그 위치에다 저장하면 되고 삭제 시에는 해당 키의 위치에 NULL값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다. 

찾고자 하는 데이터의 key만 알고 있으면 즉시 위치 찾는 것이 가능하므로 탐색, 저장, 삭제, 갱신은 모두 선형시간 O(1)로 매우 빠른 속도로 처리가 가능하다. 

다만 key 값의 최대 크기만큼 배열이 할당 되기 때문에 크기가 매우 크고 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.

2. Hash Table

Hash Table은 key-value 쌍에서 key 값 테이블에 저장할 때 Direct Addressing Table과 달리 함수를 이용해 key값의 계산을 수행한 후 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수는 해쉬 함수(Hash Function)이라고 부르며 해쉬 함수는 입력으로 key를 받아서 배열의크기-1 사이의 값을 출력한다. 

해쉬의 첫 정의대로 임의의 숫자를 배열의 크기만큼으로 변환시킨 것이다. 

이경우 k 값이 h(k)로 해쉬되었다고 하며 h(k)는 k의 해쉬값이라고 한다.

* 충돌 

해쉬  테이블은 '충돌'이 일어날 수 있다. 충돌이랑 다른 k 값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 경우를 말한다. Direct Addressing Table에서는 이를 방지하기 위해서 모든 key 값이 다르다고 전제하였지만 해쉬 테이블에서는 key 값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.

3. Open Addressing

open Addressing은 key 값을 테이블에 저장하는 Direct Addressing Table과는 다르게 모든 데이터(key+데이터)를 테이블에 저장하는 방법이다. 데이터를 모두 읽어오기 때문에 포일터를 쓸 일이 없어 포인터를 사용함으로써 발생할 수 있는 오버헤드를 방지할 수 있다. 포인터가 필요 없어서 구현이 훨씬 용이해졌으며 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상이 있다.

출처 http://hsp1116.tistory.com/35