데이터 구조 및 알고리즘: 해시 테이블

따라서 기본적으로 사전을 해시 함수에 제출하면 함수는 제공한 사전의 키와 값이 포함된 목록과 함께 값을 반환합니다. 그런 다음 목록은 메모리의 해당 값에 상주합니다.


여기서 우리는 사전의 키와 값을 가져와 함수(상자 및 기어 1)에 넣을 것입니다.

예를 들어 여기에서 {"nails":1000} 사전을 사용합니다.





해시는 값 2와 키 및 값이 있는 목록을 반환했습니다.
이 2는 기본적으로 목록이 상주할 주소입니다.




{"나사":800}도 마찬가지입니다.







{"nuts":1200}도 마찬가지입니다.






그건 그렇고 몇 가지 사항에 유의하십시오.

해시는 단방향입니다. 즉, 사전에 들어가 값과 목록을 가져오고 있음을 의미합니다. 그러나 이러한 값 및 목록을 해시 테이블로 반환하여 사전을 가져올 수 없습니다

.

또한 결정론적입니다. 즉, {"nails":1000}을 해시에 입력하면 매번 2만 반환됩니다. 다른 시간에 따라 다른 값을 제공하지 않습니다. 첫 번째로 삽입하면 2가 됩니다. 두 번째로 삽입해도 결과는 2가 됩니다....

또한 충돌 문제를 해결하기 위해 해시 테이블이나 연결 목록에 배열을 넣을 수 있습니다. 따라서 우리는 여러 양의 데이터를 가질 수 있고 여전히 동일한 출력을 얻을 수 있습니다.





또는,





건설자
크기 7의 data_map 배열을 유지할 클래스를 생성해 보겠습니다. [참고: 배열 크기는 고정되어 있습니다.]



또한 이것은 우리의 해시 방법이 될 것입니다.



모듈러스와 len(self.data_map)이 있는 이유는 크기가 7인 배열이 있고 7로 나눈 값이 있으면 0에서 6까지 알림을 받기 때문입니다. 따라서 키 값을 배열 내에 유지할 수 있습니다. 알았어요?

해시 테이블 코드:

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)


my_hash_table = HashTable()

my_hash_table.print_table()

아직 할당된 값이 없기 때문에 이와 같은 출력을 갖게 됩니다.

테이블 내에서 키와 값을 설정하는 메서드 설정

set 메서드를 포함한 전체 코드:

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    #created the set method
    def set_item(self, key, value):
        index = self.__hash(key) #cheks the index of the key
        if self.data_map[index] == None: #if there is no array already reated within the array, creates one array
            self.data_map[index] = []
        self.data_map[index].append([key, value]) #appends key and value within the array


my_hash_table = HashTable()

my_hash_table.set_item('bolts', 1400)
my_hash_table.set_item('washers', 50)
my_hash_table.set_item('lumber', 70)

my_hash_table.print_table()

키와 값 가져오기

get 코드용 코드

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)

    def set_item(self, key, value):
        index = self.__hash(key)
        if self.data_map[index] == None:
            self.data_map[index] = []
        self.data_map[index].append([key, value])


    #creating the get method
    def get_item(self, key):
        index = self.__hash(key) #looks for the index of the key
        if self.data_map[index] is not None: #if there is an array within the array, it will return the value
            for i in range(len(self.data_map[index])): #loops through the array and sets value for i using the length of it
                if self.data_map[index][i][0] == key: #if it founds the key, sends the value of it
                    return self.data_map[index][i][1]
        return None #else returns none as nothing is out there


my_hash_table = HashTable()

my_hash_table.set_item('bolts', 1400)
my_hash_table.set_item('washers', 50)

#check for values using key 
print(my_hash_table.get_item('bolts'))
print(my_hash_table.get_item('washers'))
print(my_hash_table.get_item('lumber'))

산출:



모든 키

우리가 가지고 있는 모든 키를 저장하는 방법을 만들어 봅시다.

암호:

class HashTable:
    def __init__(self, size = 7):
        self.data_map = [None] * size

    def __hash(self, key):
        my_hash = 0
        for letter in key:
            my_hash = (my_hash + ord(letter) * 23) % len(self.data_map)
        return my_hash  

    def print_table(self):
        for i, val in enumerate(self.data_map): 
            print(i, ": ", val)

    def set_item(self, key, value):
        index = self.__hash(key)
        if self.data_map[index] == None:
            self.data_map[index] = []
        self.data_map[index].append([key, value])

    def get_item(self, key):
        index = self.__hash(key)
        if self.data_map[index] is not None:
            for i in range(len(self.data_map[index])):
                if self.data_map[index][i][0] == key:
                    return self.data_map[index][i][1]
        return None


    #Keys method
    def keys(self):
        all_keys = [] #creating an array to store the keys
        for i in range(len(self.data_map)): #loops through the array
            if self.data_map[i] is not None: # checkes if the array is empty or there is an array within it
                for j in range(len(self.data_map[i])): #loops through the inside array
                    all_keys.append(self.data_map[i][j][0]) #if found an array, stores the first values within the all_key array
        return all_keys


my_hash_table = HashTable()

my_hash_table.set_item('bolts', 1400)
my_hash_table.set_item('washers', 50)
my_hash_table.set_item('lumber', 70)

print(my_hash_table.keys())

산출:



**
인터뷰 문제를 풀어봅시다.
**

A=[2,4,5] 및 B=[0,8,5] 2개의 목록이 있다고 가정합니다.
목록/배열 내에 공통적인 것이 있는지 확인하십시오.

좋습니다. 두 가지 접근 방식을 사용할 수 있습니다.

중첩된 루프를 사용하여 반복(2개의 루프가 필요하므로 O(n^2)가 됨)

이를 위한 코드:

def item_in_common(list1, list2):
    for i in list1:
        for j in list2:
            if i == j:
                return True
    return False

list1 = [1,3,5]
list2 = [2,4,6]

print(item_in_common(list1, list2))

첫 번째 배열을 사용하여 사전을 만든 다음 두 번째 배열을 사용하여 사전이 있는지 확인합니다. (이것은 O(2n)== O(n)이므로 바람직합니다)

def item_in_common(list1, list2):
    my_dict = {}
    for i in list1:
        my_dict[i] = True

    for j in list2:
        if j in my_dict:
            return True

    return False


list1 = [1,3,5]
list2 = [2,4,6]


print(item_in_common(list1, list2))

그래서, 우리는 해시 테이블을 어디에 사용했습니까? 우리는 여기에 필요하지 않았습니다. 그러나 사전은 해시 테이블의 간단한 버전입니다.

완료! 즐기자