Структура данных и алгоритмы: хэш-таблица

Итак, в основном вы собираетесь передать словарь хэш-функции, и функция вернет вам значение вместе со списком, который содержит ключ & значение предоставленного вами словаря. Затем список помещается в память на это значение.


Здесь мы собираемся взять ключ & значение словаря и поместить его в функцию (box & gear one).

Например, используя здесь словарь {«nails»:1000}


хэш возвращает значение 2 & список с ключом & значением.
Эта 2 — по сути, адрес, где будет находиться список.


То же самое для {«шурупы»:800}

, то же самое для {«гайки»:1200}


Кстати, обратите внимание на несколько моментов:

  1. Хэш является односторонним: Это означает, что вы вводите словарь и получаете значение и список. Но вы не можете вернуть эти значение и список в хэш-таблицу, чтобы получить словарь.

  2. Также он детерминирован: Это означает, что если вы поместите {«nails»:1000} в хэш, каждый раз он будет возвращать только 2. Он не будет выдавать разные значения в зависимости от разного времени. Если вы вставите его в первый раз, вы получите 2. Во второй раз все равно получится 2 и так далее…….

Также, чтобы решить проблему коллизий, мы можем поместить массив внутрь нашей хэш-таблицы или связного списка. Таким образом, мы можем иметь множество данных и получить один и тот же результат.

или,

Конструктор
Создадим класс, в котором будет храниться массив data_map размером 7. [Примечание: размеры массивов фиксированы].

Также это будет наш метод хэширования:

Причина, по которой мы использовали модуль и 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 для установки ключей и значений в таблице

весь код, включая метод 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())

Вход в полноэкранный режим Выйти из полноэкранного режима

Выход:

**
Решим задачу на собеседование:
**

Предположим, что у вас есть 2 списка A=[2,4,5] и B=[0,8,5].
Проверьте, есть ли что-то общее в этих списках/массивах:

Итак, у нас может быть 2 подхода:

  1. Использовать вложенный цикл для итерации (Нам понадобится 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))
Войти в полноэкранный режим Выйти из полноэкранного режима
  1. Создайте словарь, используя первый массив, а затем, используя второй массив, проверьте, есть ли он там. (Это будет иметь 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))
Войти в полноэкранный режим Выход из полноэкранного режима

Итак, где мы использовали хэш-таблицу, верно? Здесь нам это не понадобилось. Но словарь — это простая версия хэш-таблицы.

Готово! Давайте наслаждаться

Оцените статью
devanswers.ru
Добавить комментарий