Hash-Table

앞에서 Direct Acess Table 은 자칫 잘못하면 메모리 공간을 낭비 한다고 했는데, 이러한 시간과 메모리 둘다 효율적으로 사용하는 Hash Table = (해쉬 함수와 배열을 같이 사용) 한 인덱스에 키와 벨류를 모두 저장함.

해쉬함수의 조건

해쉬 함수 나누기 방법

def def hash_function_remainder(key, array_size):
    """해시 테이블의 key를 나누기 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
	return key % array_size 
    #key를 200으로 나누어서 남는 나머지를 리턴한다는 거죠. 
    #40을 넣으면 40, 120은 120, 788 은 180, 2307은 107가 리턴됩니다.

해쉬 함수 곱셈 방법
1. 0 ~ array_size < 1 사이의 임의의 소수점 값 a
2. temp = 임의의 소숫점 값 a key 값
3. temp = temp - int(temp) 소숫점 오른쪽만 남김
4. 자연수 = return int(temp 배열의 크기)

def hash_function_multiplication(key, array_size, a):
    """해시 테이블의 key를 곱셈 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
    temp = a * key # a와 key를 곱한다 
    temp = temp - int(temp) # a와 key를 곱한 값의 소숫점 오른쪽 부분만 저장한다
    return int(temp * array_size) # temp와 배열 크기를 곱한 수의 자연수 부분만 리턴한다

1. 즉 해쉬함수 는 결정론적이어야 된다.
2. 원하는 범위의 자연수 하나하나가 리턴될 확률이 최대한 비슷해야 된다.
3. 빨리 계산을 할 수 있어야 된다.

해쉬 함수는 같은 값을 넣으면 항상 같은 정수를 리턴해주는 함수 hash 함수를 사용해서 해시 테이블에 key가 문자열인 데이터를 저장할 건데요. 그 때 그냥 “아 문자열을 고유한 정수 값으로 바꿔주는구나”라고 이해하시면 됩니다!!

불변형 자료형에만 Hash 함수를 사용 할 수 있음.