[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 10회차 미션

6.2 Linear Probing 기법

-> 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결

-> 충돌이 일어나면 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장

- 저장공간 활용도를 높이기 위한 기법

           연습3: 연습1의 해쉬 테이블 코드에 Linear Probling 기법으로 충돌해결 코드를 추가

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

 

def get_key(data):

    return hash(data)

 

def hash_function(key):

    return key % 8

 

def save_data(data, value):

    index_key = get_key(data)

    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:

        for index in range(hash_address, len(hash_table)):

            if hash_table[index] == 0:

                hash_table[index] = [index_key, value]

                return

            elif hash_table[index][0] == index_key:

                hash_table[index][1] = value

                return

    else:

        hash_table[hash_address] = [index_key, value]

 

def read_data(data):

    index_key = get_key(data)

    hash_address = hash_function(index_key)

   

    if hash_table[hash_address] != 0:

        for index in range(hash_address, len(hash_table)):

            if hash_table[index] == 0:

                return None

            elif hash_table[index][0] == index_key:

                return hash_table[index][1]

    else:

        return None

print (hash('dk') % 8)

print (hash('da') % 8)

print (hash('dc') % 8)

출력 : 4 4 4

save_data('dk', '01200123123')

save_data('da', '3333333333')

read_data('dc')

 

6.3 빈번한 충돌 개선하는 기법

-- 해쉬 함수를 재정의 및 해쉬 테이블 저장 공간 확대

 hash_table = list([None for i in range(16) ] )

def hash_function(key);

           return key% 16

 참고: 해쉬 함수와 키 생성 함수

     python의 hash() 함수는 실행할 때마다 값이 달라질 수 있다

     유명한 해쉬함수들이 있음: SHA( Secure Hash Algorithm 안전한 해쉬 알고리즘)

-      어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로 해쉬 함수로 유용하게 활용 가능

SHA-1

import hashlib

 

data = 'test'.encode()

hash_object = hashlib.sha1()

hash_object.update(data)

hex_dig = hash_object.hexdigest()

print (hex_dig)

 

SHA-256

import hashlib

 

data = 'test'.encode()

hash_object = hashlib.sha256()

hash_object.update(data)

hex_dig = hash_object.hexdigest()

print (hex_dig)

 

 

 

 

연습 4 : 해쉬 테이블 코드에 키 생성 함수를 SHA-256 해쉬 알고리즘을 사용하도록 변경

 

import hashlib

 

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

 

def get_key(data):

        hash_object = hashlib.sha256()

        hash_object.update(data.encode())

        hex_dig = hash_object.hexdigest()

        return int(hex_dig, 16)

 

def hash_function(key):

    return key % 8

 

def save_data(data, value):

    index_key = get_key(data)

    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:

        for index in range(hash_address, len(hash_table)):

            if hash_table[index] == 0:

                hash_table[index] = [index_key, value]

                return

            elif hash_table[index][0] == index_key:

                hash_table[index][1] = value

                return

    else:

        hash_table[hash_address] = [index_key, value]

 

def read_data(data):

    index_key = get_key(data)

    hash_address = hash_function(index_key)

   

    if hash_table[hash_address] != 0:

        for index in range(hash_address, len(hash_table)):

            if hash_table[index] == 0:

                return None

            elif hash_table[index][0] == index_key:

                return hash_table[index][1]

    else:

        return None

 

print (get_key('db') % 8)

print (get_key('da') % 8)

print (get_key('dh') % 8)

 

save_data('da', '01200123123')

save_data('dh', '3333333333')

read_data('dh')

 

 

7. 시간 복잡도

   -> 일반적인 경우는 O(1)

   -> 최악의 경우는 O(n)

   해쉬 테이블의 경우 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG