Хэш таблица

@Baumanetc · Регистрация: 11.11.2019

Студворк — интернет-сервис помощи студентам

Здравствуйте

Помогите вот с такой задачей:

Заполнить хэш-таблицу для следующего набора данных:
'Водоросли': 280
'Картофель': 260
'Лук-порей': 59
'Манго': 291
'Орехи грецкие': 266
'Салями': 225
'Специи': 283
'Сыр сливочный': 152
'Творог': 215
'Тофу': 142
'Хек': 248
'Чай черный': 118
'Чернила каракатицы': 95
'Шампиньоны': 101
'Финик': 104

Хэш функция работает следующим образом: вычисляет длину ключа (название - name) делит на 20 – получившийся остаток от деления является хэшем.

Python
1
2
3
def hashFunction(name):
    n = len(name) % 20
    return n

Для разрешения коллизий использовать метод открытой адресации (линейное пробирование).
После добавления всего набора данных выполнить удаление из хэш-таблицы следующих данных, в том порядке, в котором они представлены:
'Орехи грецкие': 266
'Водоросли': 280
'Специи': 283
'Манго': 291

@Welemir1 · 27.09.2020, 16:06

Сообщение от Baumanetc

Помогите вот с такой задачей:

как помочь? вроде подробно расписано и даже функция хеша есть

@Baumanetc · 28.09.2020, 13:34 **[ТС]**

Исходные данные я попробовал рассмотреть как словарь. Написал вот такой код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
m = {'Водоросли': 280,
     'Картофель': 260,
     'Лук-порей': 59,
     'Манго': 291,
     'Орехи грецкие': 266,
     'Салями': 225,
     'Специи': 283,
     'Сыр сливочный': 152,
     'Творог': 215,
     'Тофу': 142,
     'Хек': 248,
     'Чай черный': 118,
     'Чернила каракатицы': 95,
     'Шампиньоны': 101,
     'Финик': 104}
 
 
def hashFunction(name):
    n = len(name) % 20
    return n
 
 
for i in m.keys():
    print(hashFunction(i))

Хэш-таблица в python, я так понимаю, это массив. Хэш-функция мне возвращает индекс элемента в этом массиве, по которому мне нужно положить данные ('Водоросли': 280, 'Картофель': 260 и т.д.) попутно разрешая коллизии. Вот это и вызвало сложности: как корректно сформировать массив - хэш таблицу

@Welemir1 · 02.11.2020, 15:09

Сообщение от Baumanetc

Хэш-таблица в python, я так понимаю, это массив.

нет это словарь
мне кажется от тебя хотят чтобы ты написал свой словарь (отнаследовался от стандартного), то есть создал класс и все вот эти вещи делал внутри него, нет?

Рыжий Лис · 02.11.2020, 16:40

Сообщение от Welemir1

(отнаследовался от стандартного),

нет

Добавлено через 9 минут
С коллизиями:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyHashTable:
    size = 20
    
    def __init__(self):
        self._data = [None for _ in range(self.size)]
 
    def __getitem__(self, key):
        h = self.__get_hash(key)
        return self._data[h]
 
    def __setitem__(self, key, value):
        h = self.__get_hash(key)
        self._data[h] = value
 
    def __get_hash(self, name):
        return len(name) % self.size
 
m = {'Водоросли': 280,
     'Картофель': 260,
     'Лук-порей': 59,
     'Манго': 291,
     'Орехи грецкие': 266,
     'Салями': 225,
     'Специи': 283,
     'Сыр сливочный': 152,
     'Творог': 215,
     'Тофу': 142,
     'Хек': 248,
     'Чай черный': 118,
     'Чернила каракатицы': 95,
     'Шампиньоны': 101,
     'Финик': 104}
 
table = MyHashTable()
for k, v in m.items():
    table[k] = v
print(table['Манго'])
print(table._data)
# 104
#[None, None, None, 248, 142, 104, 215, None, None, 59, 101, None, None, 152, None, None, None, None, 95, None]

@Baumanetc · 08.11.2020, 19:38 **[ТС]**

Рыжий Лис, большое спасибо за код. Попробую разобраться с коллизиями

@Baumanetc · 10.11.2020, 20:02 **[ТС]**

Попробовал разобраться с коллизиями. Я так понимаю, что если индекс занят, то помещаем элемент на следующий свободный. Сделал вот так:

Python
1
2
3
4
5
6
7
8
    def __setitem__(self, key, value):
        h = self.__get_hash(key)
        if self._data[h] is None:
            self._data[h] = value
        elif self._data[h] is not None and self._data[h+1] is None:
            self._data[h+1] = value
        else:
            self._data[h+2] = value

Не все попадает, но я хотя бы в верном направлении мыслю? Помогите, пожалуйста, еще немного. Одно задание осталось сдать.

@Baumanetc · 15.11.2020, 20:21 **[ТС]**

Разобрался с коллизиями.

Python
1
2
3
4
5
6
7
8
9
10
    def __setitem__(self, key, value):
        h = self.__get_hash(key)
        if self._data[h] is None:
            self._data[h] = value
        else:
            next_h = self.__get_rehash(h)
            while self._data[next_h] is not None and self._data[next_h] != value:
                next_h = self.__get_rehash(next_h)
            if self._data[next_h] is None:
                self._data[next_h] = value

Python
1
2
    def __get_rehash(self, oldhash):
        return oldhash + 1

В результате получил вот такой массив:
[None, None, None, 248, 142, 291, 225, 283, 215, 280, 260, 59, 118, 266, 152, 101, 104, None, 95, None]

Чтобы корректно получать из него значения я так понимаю мне нужно вот этот код модифицировать

Python
1
2
3
    def __getitem__(self, key):
        h = self.__get_hash(key)
        return self._data[h]

Вот тут реально не знаю, как сделать. Может кто-нибудь идею подкинет?

@Baumanetc · 17.11.2020, 16:41 **[ТС]**

Рыжий Лис, без вашей помощи мне не справиться. Подскажите, пожалуйста, еще немного

@Baumanetc · 18.11.2020, 20:28 **[ТС]**

Вроде разобрался с получением значения по ключу. Остался последний этап - удаление.

@Baumanetc · 26.11.2020, 18:38 **[ТС]**

Переписал немного код класса. Теперь в свою хэш таблицу я на каждый индекс помещаю словарь.
[None, None, None, {'key': 'Хек', 'value': 248}, {'key': 'Тофу', 'value': 142}, {'key': 'Манго', 'value': 291}, {'key': 'Салями', 'value': 225}, {'key': 'Специи', 'value': 283}, {'key': 'Творог', 'value': 215}, {'key': 'Водоросли', 'value': 280}, {'key': 'Картофель', 'value': 260}, {'key': 'Лук-порей', 'value': 59}, {'key': 'Чай черный', 'value': 118}, {'key': 'Орехи грецкие', 'value': 266}, {'key': 'Сыр сливочный', 'value': 152}, {'key': 'Шампиньоны', 'value': 101}, {'key': 'Финик', 'value': 104}, None, {'key': 'Чернила каракатицы', 'value': 95}, None]

Сделал функцию удаления

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    def delete(self, key):
        h = self.get_hash(key)
        if self.data[h]["key"] == key:
            self.data[h] = None
            return
 
        h_next = self.get_rehash(h)
        try:
            while self.data[h_next] is not None:
                if self.data[h_next]["key"] == key:
                    self.data[h_next] = None
                    break
                h_next = self.get_rehash(h_next)
        except IndexError:
            raise
        self.data[h_next] = None

После удаления функция на место удаленного элемента помещает "дырку", что не совсем правильно. Например, я удаляю элемент "Водоросли". Соответственно, на индексе 9 будет None и если я потом захочу получить данные по "Картофель" или "Лук-порей", то вернется None, т.к. у них хэш тоже 9. Может кто поможет доработать код так, чтобы, если нужно, элементы сдвигались? Буду очень благодарен

@Baumanetc · 29.11.2020, 00:55 **[ТС]**

В общем, вот мой код целиком:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class HashTable:
    size = 20
 
    def __init__(self):
        self.data = [None] * self.size
 
    def __getitem__(self, key):
        h = self.get_hash(key)
        try:
            while self.data[h]:
                if self.data[h] and self.data[h]["key"] == key:
                    return self.data[h]
                h = self.get_rehash(h)
        except IndexError:
            return
 
    def __setitem__(self, key, value):
        h = self.get_hash(key)
        if self.data[h] is None:
            self.data[h] = {"key": key, "value": value}
            return
 
        next_h = self.get_rehash(h)
        try:
            while self.data[next_h] is not None:
                if self.data[next_h]["key"] == key:
                    self.data[next_h]["key"] = value
                    break
                next_h = self.get_rehash(next_h)
        except IndexError:
            raise
        self.data[next_h] = {"key": key, "value": value}
 
    def get_hash(self, name):
        return len(name) % self.size
 
    def get_rehash(self, oldhash):
        return oldhash + 1
 
    def delete(self, key):
        h = self.get_hash(key)
        if self.data[h]["key"] == key:
            self.data[h] = None
            return
 
        h_next = self.get_rehash(h)
        try:
            while self.data[h_next] is not None:
                if self.data[h_next]["key"] == key:
                    self.data[h_next] = None
                    break
                h_next = self.get_rehash(h_next)
        except IndexError:
            raise
        self.data[h_next] = None

Если у кого-то есть идеи, как удалять элементы и делать смещение (если это необходимо), то поделитесь, пожалуйста

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@Baumanetc 5 / 5 / 1 Регистрация: 11.11.2019 Сообщений: 143 Записей в блоге: 2
	08.11.2020, 19:38 [ТС]
	Рыжий Лис, большое спасибо за код. Попробую разобраться с коллизиями 0

@Baumanetc 5 / 5 / 1 Регистрация: 11.11.2019 Сообщений: 143 Записей в блоге: 2
	17.11.2020, 16:41 [ТС]
	Рыжий Лис, без вашей помощи мне не справиться. Подскажите, пожалуйста, еще немного 0

@Baumanetc 5 / 5 / 1 Регистрация: 11.11.2019 Сообщений: 143 Записей в блоге: 2
	18.11.2020, 20:28 [ТС]
	Вроде разобрался с получением значения по ключу. Остался последний этап - удаление. 0