Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- using namespace std;
- struct node { //структура записи
- int index;
- string name;
- node* next;
- };
- class HashTable {
- public:
- node* table;
- int size=1000;
- HashTable() {
- table = new node[size]; //выделяем память под массив списков
- }
- int hash_function(int key) {
- return key % 1000; //идеальная хеш функция, если городов меньше 1000 и каждый имеет уникальный ID, иначе коллизии
- }
- void add(int key, string name) {
- int index = hash_function(key);
- node* temp = new node; //забиваем в структуру записи
- temp->index = key;
- temp->name = name;
- if(table[index].next == NULL) {
- table[index].next = temp; //если было в ячейке пусто
- } else {
- node* temp2 = table[index].next;
- while(temp2->next != NULL) {
- temp2 = temp2->next; //если не пусто, идем до конца, хотя можно было бы и в начало вставлять(это может спросить), в начало немного эффективнее по времени(нет цикла), скажешь что ну так захотелось
- }
- temp2->next = temp;
- }
- }
- node get(int key,string name) {
- int index = hash_function(key);
- node* temp = table[index].next; //получаем элемент хеш таблицы за постоянное время, далее проверяем все колизии (стоит учесть что это пустой элемент, а не коллизия)
- while(temp != NULL) {
- temp = temp->next;
- if(temp->name== name) { //если коллизий нет, то цикл пройдет 1 итерацию, если есть, то идем пока не найдем нужное имя
- return *temp;
- }
- }
- node nn = {-1, "NOT FOUND", NULL}; //если не нашли ниче, вернем ошибку
- return nn;
- }
- };
- void print_node(node n) {
- cout << n.index << " " << n.name << endl; //просто вывод структуры на экран
- }
- int main()
- {
- HashTable ht;
- ht.add(1, "John"); //забиваем
- ht.add(1, "Jane");
- ht.add(1, "Jack");
- ht.add(4, "Jill");
- print_node(ht.get(1, "Jack"));//ищем
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement