[파이썬 코테 대비 동아리] _개념을 공부하자 "해시"편

해쉬

해시(Hash) 란?

: 자료구조의 하나이다. 임의 값을 ( a, 124, 안녕하세요, Hello World ) 해시( Hash ) 함수로 일정한 길이의 값으로 바꾸는 것이다.

해시 테이블( Hash Table )이란?

: 해시 함수를 사용하여 출력값인 색인( index )을 이용해 key 와 value로 저장된 해시 테이블에서 데이터를 찾는다. 데이터를 다루는 기법 중 하나로 데이터의 검색과 저장이 빠르게 진행된다 .

파이썬에서는 dictionary, 루비에서는 Hash, 자바에선 Map이 해시 테이블의 대표적인 예시이다. 보통은 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용한다. ( 공간과 탐색 시간을 맞바꾸는 기법) 그러나 파이썬에서는 해시 테이블 사이즈를 딕셔너리 타입을 쓰면 끝이기 때문에 별도로 구현할 필요가 없다 !

: 기본 연산으로는 search, insert, delete가 있다.

: 순차적으로 데이터를 저장하지 않고 key를 통해서 value 값을 얻는다.

: slot이란 단어를 종종 볼 수 있는데 slot은 해시 테이블에서 한 개의 데이터를 저장할 수 있는 공간이다.

: 쉽게 말하면 데이터 테이블 같은 느낌인 듯 ?

1. 해시는 자료구조의 하나
2. key를 이용해서 해시함수를 거치면 출력값 ( index )가 나오는데 이를 해시 주소라고 하며, 해시 테이블에서 해시 주소를 대입하면 데이터 위치를 일관성 있게 찾을 수 있다.
3. 해시 테이블의 한 개의 데이터 저장 공간을 슬롯( slot )이라고 부른다.
4. 데이터 검색과 저장이 아주 빠르게 진행되기 때문에 많이들 쓴다 !
5. 주로 검색이 많이 필요한 경우 / 저장, 읽기, 삭제가 빈번한 경우 / 캐쉬 구현시에 많이 쓴다.

Dictionary를 쓰기 전에.. 초간단 해시 함수를 한번 만들어보자

hash_table = list([ 0 for i in range(10)])
hash_table

#output
#[0,0,0,0,0,0,0,0,0,0]

해시 함수 ?

: 임의의 길이를 갖는 메시지를 입력 받아서 고정된 길이의 해시값을 출력하는 함수이다. 원래 입력 값과는 완전히 다른 모습이기 때문에 암호화 영역에서 주요하게 사용되며 SHA ( Secure Hash Algorithm )알고리즘이 대표적인 예시이다 .

: 가끔… 해시 충돌이 일어난다. 고정된 해시값을 출력하기 때문에 다른 값을 입력해도 같은 해시값이 나오는 것이다. 이를 해결하기 위해서는 별도의 자료구조가 필요하다.

해시 충돌 방지

: 개방 주소법(open addressing)으로 해시 테이블 크기는 고정하면서 빈 곳을 찾아 채우거나 분리 연결법(seperate chaining)으로 해시 테이블의 크기를 가변적으로 만드는 방법이다.

개방 주소법(open addressing)

: 선형 탐사법(Linear Probing)으로 선형적이게 순차적으로 검색한다. slot에 이미 값이 저장되어 있으면 이 slot만큼 폭을 옮겨 다음 해시값에 저장한다.

또는 제곱 탐사법(Quadratic Probing)으로 고정폭이 아닌 제곱으로 폭을 늘리는 방법이다. 또는 이중 해싱(Double Hashing) 으로 해시값의 규칙을 없앤다. 충돌된 해시에 또 해시를 적용해서 값을 다르게 변화시키는 것이다.

분리 연결법(seperate chaining)

: 하나의 슬롯에 들어갈 값의 제한을 듣지 않는다. 이때 slot 에는 linked list 나 tree를 이용해준다. linked list로 노드가 연결되기 때문에 (기차라고 생각한다 나는…) 주소가 변하지 않고 데이터 개수 제약이 없다. 하지만 메모리 문제가 있을 수 있다.

파이썬에서의 해시 테이블. 딕셔너리(Dictionary)

: 먼저 딕셔너리에 대해서 살펴보자

value1 = {
	'color' : 'green'.
	'age' : '24'.
	'address' :'Seoul'
}

print(value1) #전체 출력
print(value1.keys()) #key만 출력
print(value1.values()) # value만 출력
print(value1['age']) # key로 값에 접근
value1['grade'] = 5 # key값 추가
value1['grade'] =7 #값 수정
del value1['grade'] # key값 삭제

이제 key와 value를 출력 해보자.

for key, value in value1.items(): #item함수는 딕셔너리의 key value반환
	print("key :"+key)
	print("value: "+value)
	print("키에 따른 값 :" +user[key]

위는 딕셔너리의 구조와 정의 사용법이다.

hash_table = list([0 for i in range(10)])
print(hash_table)

def hash_func(key):
    return key % 5

data1 = "red"
data2 = "yellow"
data3 = 'blue'

print(ord(data1[0]), ord(data2[0]), ord(data3[0]))
print(ord(data1[0]), hash_func(ord(data1[0])))

def save_data(data, value):
    key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

save_data("red", "1000")
save_data("yellow", "2000")
save_data("blue", "3000")

def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]

print(get_data("red"))

이런식으로 hash로 dictionary를 이용해 값에 접근할 수 있다.

우리의 목표는 뭐다 ? 코딩 테스트다

해시가 뭔지 다 알아봤으니 이제 몸으로 느껴보자 !

https://codingpractices.tistory.com/entry/Python-파이썬-해시-Hash-해싱-Hashing-문제로-알아보기

여기서 풀이를 가져옴 …! 왜냐면..난…아무것도 모르니까..배우는 의미로다가…

프로그래머스 Level2 전화번호 목록

:전화번호부의 전화번호 중 한 번호가 다른 번호의 접두어인 경우 확인.

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

다음의 전화번호의 경우 구조대의 번호가 영석이의 접두사이다.

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution함수의 매개변수로 주어질 때 어떤번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true 를 return 하도록 solution함수를 작형한다.

해시 x 풀이

def soulution(phone_book):
	answer = True
	for i in phone_book:
		temp=''
		for j in i:
			temp += j
			if temp in phone_book and temp != i:
				answer = False
			return answer

이러면 효율성 문제에서 오류가 난다구 하네요 ~

해시 o 풀이

def solution(phone_book):
	answer = True
	hash = {}

	for i in phone_book:
		hash[i] = 1
	for i in phone_book:
		temp = ''
		for j in i:
			temp += j
			if temp in hash and temp !=i:
			answer = False

	print(answer)

solution(['119','97676223','1195524421'])
solution(['123','456','789'])

사실 봐도 이해가 잘 안 됨 ㅠ-ㅠ

꾸역꾸역 노력해보자면…

hash i값에 1을 담는 이유는 value값이 필요없고 key값만 비교하면 되는 문제이기 때문인 것 같다. 딱히 다른 값도 없고 전번만 비교하면 되기 때문에.. 그래서 temp(임시)변수에다 값 너어가며 hash로 비교해가면서 같은 게 있나 없나 검사하는 거 같은데…어…….ㅠㅠㅠㅠㅠㅠ모르겠다..

다른 블로그의 문제풀이와 해설을 또 가져오봤다

https://scarletbreeze.github.io/articles/2019-07/pythonKit문제풀이(1)

완주하지 못한 선수

• 수많은 사람들이 선수들이 마라톤에 참여
• 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주
• 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,
• 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요
• 제한사항
• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하
  • participant의 길이는, 10만 이하를 가질 것이네.
• completion의 길이는 participant의 길이보다 1 작다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다.
• 참가자 중에는 동명이인이 있을 수 있다.
  • 동명이인 조건이 없었다면, 집합으로 구해서 차집합으로 구해버리면 되는데, 이 조건을 인해 접근 방법이 달라짐
• 입출력 에시도 잘 살펴보기

일단 해설보기 전 내 생각은 마라톤선수 참가선수 배열과 완주 선수 배열을 비교해서( 참가선수 해시에 value값을 모두 0으로 설정 ) 단 한명의 선수 제외하고는 해시 value값이 1로 들어가게끔 만들어주고 해시찾기로 value값이 1인 사람을 출력하게끔 하면 되겠는데 음…

동명이인을 어떻게 할까 ㅠ가 문제이다.

해설을 보니 !!! 이런 생각이 …!!! 참가 선수 이름을 a b c d라고 하면 참가 선수에 value에 이름이 나올 때 마다 1을 증가시켜준다. 만약 b가 3명이라 하면 참가 선수만 등록한 해시에는 value가 3이 들어감. 이제 완주 선수 해시를 비교해서 1씩 감소시켜주면 …!! b만 1을 가지기 때문에 리턴값(key)을 호출하면 b가 나온다 !!

def solution(participant, completion):
	table = { } # 빈 딕셔너리 == 해시 테이블 만들고
	for x in participant :
		table[x] = table.get(x,0) + 1 #key로 value얻어내느 함수 get 사용. 딕셔너리에 x가 없을시 default 입력, 처음 등장하면 1로 만들고 아니면 기존 value에 1 더하기
	for x in completion :
		table[x] -= 1  #완주 인원 빼주기
	tablenf = [ i for i , k in table.items() if k > 0]
	answer = dnf[0]
	return answer

다른건 다 이해했는데 7번째 줄 이해불가..ㅠ 파이썬 이해부족인듯 파이썬을 개념부터 안 하고 그냥 찍먹수준으로 필요한 것 만 골라 공부했더니..뭔지 모르겠다…

일단 items()함수가 key 의 value만 반환한다.

dnf라는 변수는 배열이며 k와 딕셔너리의 …. 이부분 이해가 안댐 ㅠ0ㅠ

i for i 가 i 를 리스트 안에 넣는데... items()로 밸류 값 뽑아내서 1이상이면 k가 되고 그 k를 i에 넣는다는건가….?

 

아@@@ 알아냈다 i 를 리스트 안에 넣는데 key i의 value값 k를items로 1보다 큰 밸류 가 있으면 key값 i를 넣는다 !! 라는 듰 인듯 !!