[알고리즘 스터디] 해쉬 (Hash)

후후 필자는 코딩 문법만 안다고 해서 모든게 해결되지 않는 다는 것을 깨닫게 되어 알고리즘 스터디를 시작하였다.

다들 현직자분들이신데.. 나만 비전공자에 IT 업종이 아니다.. 

스터디에 폐를 끼치지 않기 위해 해시 개념에 대해 공부 내용을 작성한다. 

(참고로 회사에서 자칭 IQ 300이 기본적인 개념 설명도 알려주었다!!)

 

*해쉬: 알고리즘의 복잡성을 가장 줄여주는 효과적인 자료 구조

용어 

• 해쉬 (Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 함수 (Hash Function): 특정 연산을 이용하여 키 값을 받아서 value를 가진 공간의 주소로 바꿔주는 함수
• 해쉬 테이블 (Hash Table): 해쉬 구조를 사용하는 데이터 구조

Harsh 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 색인 (Index) 혹은 주소 삼아 데이터 값 (Value)을 키와 함께 저장하는 자료구조

-> 해싱을 한 후 직접 접근이 가능한 구조 

 

 Keys--------------------->Hash function ------------------> Buckets

[이름]                             [해싱 과정]                 [Index(hash value) : data]

 

• 해쉬 값 (해쉬 주소, Hash Value or Address): Key 값을 해쉬 함수에 넣어서 얻은 주소 값
• 슬롯 (Slot): 한 개의 데이터를 저장할 수 있는 공간

해쉬(Hash)

• 데이터를 다루는 기법 중 하나, 검색과 저장을 아주 빠르게하는 자료구조
• 데이터를 저장할 때, key-value 형태로 데이터가 존재, Key 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어나게 된다. 
• 파이썬 -> 딕셔너리 (Dictionary) 타입과 같은 구조 ->일관성을 유지하여 apple 4, banana 5를 무조건 유지
• 문자열(String)을 받아서 숫자를 반환하는 함수
• 함수는 문자열에 대해 숫자를 Mapping(할당)
• 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위해 별도 자료구조가 필요함 (충돌 해결)
• 저장공간이 좀 더 많이 필요 

파이썬에서 사용 시,

기본 라이브러리 hash() 함수 사용

Hashlib 라이브러리는 SHA 함수들을 가지고 있는 라이브러리

SHA (Secure Hash Algorithm): 어떤 데이터도 고정된 크기의 유일한 값으로 리턴해줌

SHA-1 예시

SHA-256 예시

ehxdigest() : Return to encoded data in hexadecimal format

딕셔너리 문법

리스트로 만든 개선된 해쉬테이블 (충돌 해결 알고리즘)

1. Chaining 기법

Open Hashing 기법 중 하나: 해쉬 테이블 저장 공간 외에 공간을 더 추가해서 사용하는 방법

충돌 발생 시, 링크드 리스트로 데이터를 추가로 뒤에 연결시키는 방법

 

2. Linear probing 기법

Hash table 저장 공간 안에서 충돌 문제를 해결하는 방법

 

3. 공간을 확장하는 방법

n을 생성자의 매개변수로 사용해서 받고, 해당 n을 큰 수로 늘린다면 많은 공간을 사용할 수 있음

 

 

딕셔너리 객체의 get() 메소드

dict.get(key, default=none)

get 메소드의 리턴 값은 첫번째 인자인 키 값 

 

 

 

https://www.youtube.com/watch?v=xls6jEZNA7Y