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

3. 간단한 해쉬의 예

           3.1 hash table 만들기

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

                      hash_table

           3.2 이번엔 초간단 해쉬함수 만들기

                      다양한 해쉬 함수 고안 기법이 있다

                      가장 간단한 방식이 Division 법

                      def hash_func(key):

                                 return key%5

           3.3 해쉬 테이블에 저장

                      데이터에 따라 필요시 key 생성 방법 정의 필요

                      data1 = ‘Andy’

                      data2 = ‘Dave’

                      data3 = ‘Trump’

                      data4 = ‘Anthor’

                      ## ord( ) : 문자의 ASCII 코드 리턴

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

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

                      print( ord ( data1[ 0 ] ), ord( data4 [ 0 ] )

                      3.3.2 해쉬 테이블에 값 저장 예

                  -> data:value 와 같이 data 와 value를 넣으면 해당 datad에 대한 key를 찾아서

                        해당 key에 대응하는 해쉬주소에 value를 저장하는 예

                        def storage_data( data, value) :

                                 key = ord (data[0] )

                                 hash_address = hash_func(key)

                                 hash_table [ hash_address ]  =value

                      3.4 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수를 만들어보자

                                 storage_data (‘Andy’, ‘01012345678’)

                                 storage_data(‘Dave’, ‘01043218765’)

                                 storage_data(‘Trump’ , ‘0101241415’)

                      3.5 실제 데이터를 저장하고 읽어보자

                                 def get_data(data):

                                    key = ord( data[ 0 ] )

                                    hash_address = hash_func (key)

                                   return hash_table[hash_address]

                                 get_data[‘Andy’]

           4. 자료 구조 해쉬 테이블의 장단점과 주요 용도

                      - 장점

                      ->데이터 저장/읽기 속도가 빠르다

->해쉬는 키에 대한 데이터가 있는지 확인이 쉬움

    - 단점

->일반적으로 저장공간이 좀 더 많이 필요

->여러키에 해당하는 주소가 동일할 경우 충동을 해결하기 위한 별도 자료구조가 필요

   - 주요 용도

검색이 많이 필요한 경우

저장, 삭제, 읽기가 빈번한 경우

캐쉬 구현시

           5. 프로그래밍 연습

                      연습1 : 리스트 변수를 활용해 해쉬 테이블 구현하기

                                 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):

                                             hash_address = hash_function( get_key9(data ))

                                             hash_table [hash_address] =value

                                 def read_data ( data) :

                                             hash_address = hash_function(get_key(data))

                                             return hash_table[ hash_address ]

                                 save_data(‘Dave’ , ‘0102030200’ )

                                 save_data(‘Andy’ , ‘01033232200’)

                                 read_data(‘Dave’)

                                 hash_table

6. 충돌해결 알고리즘( 좋은 해쉬 함수 사용하기)

                      해쉬 테이블의 가장 큰 문제는 충돌의 경우

                      이 문제를 충돌 또는 해쉬 충돌이라고 부릅니다

6.1 Chaining 기법

-  개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용

-  충돌이 일어나면 링크드 리스트라는 자료 구조를 사용해 링크드 리스트로 데이터를 추가로

뒤에 연결시켜 저장

           연습2 : 연습 1의 해쉬 테이블 코드에 Chaining 기법으로 충돌해결 코드 추가

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(len(hash_tavle[hash_address])):

                                 if hash_table [hash_address][index][0] == index_key:

                                   hash_table [hash_address][index][1] = value

                                   return

                      hash_table[hash_address].append( [ index_key, value] )

           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:

 

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

https://bit.ly/2FgOONG