Сравнете таблицата хашиш и Mar на шаблон библиотека стандарт (STL). Как е хеш таблицата? Какво структурата на данните е оптимална за малки обеми от данни?
В таблицата с хеш стойност пада, когато се обадите хеш бутона. Самите стойности се съхраняват в несортиран ред. От хеш таблицата използва ключ за индексиране елементи, вмъкване или извличане на данни отнема O (1) време (като се вземат предвид минималния брой сблъсъци в хеш таблици). хеш таблицата също така трябва да се справят с потенциален конфликт. За тази цел веригата - свързан списък на всички ценности и ключовете са показани в даден индекс.
карта (STL) вмъква ключ / стойност двойки в двоичен дърво търсене въз основа на ключове. Няма нужда да се справи с конфликта, както и дървото е балансиран, вмъкване и да търсите време е O (влезте N).
Как да се приложи хеш-таблица?
Таблица хеш е изпълнен като множество от свързани списъци. Когато искаме да поставите двойка ключ / стойност, а след това, с помощта на функцията за сегментиране картографиране на ключа в индекса на масива. Когато тази стойност пада до определена позиция на свързан списък.
Не можем да кажем, че елементите на свързан списък с конкретен индекс масив са един и същ ключ. По-скоро, hashFunction (ключ), функция за тези стойности съвпадат. Ето защо, за да се получи стойност, съответстваща на ключа, ние трябва да се съхраняват в един възел и ключа и стойност.
За да обобщим: хеш таблицата се реализира като масив от свързани списъци, всеки възел в списъка съдържа два компонента: стойността на оригиналния ключ. Нека изброим характеристиките на изпълнението на хеш таблици:
- Трябва да се използва добра хеш функция, за да се гарантира, че ключовете са били правилно разпределени. Ако ключовете са лошо разпределени, ще има много конфликти и скоростта на понижения на елемента.
- Без значение колко добър нашата хеш функция, конфликти ще възникнат, и ние ще трябва да подходят към тях. Това включва използването на свързани вериги списъци (или друг метод за решаване на проблема).
- Възможно е да се прилагат методите, динамично увеличават или намаляват размера на хеш таблицата. Например, когато съотношението на елементите на размера на таблицата надвиши определена стойност, е необходимо да се увеличи размера на таблицата на хеш. Това означава, че ние трябва да се създаде нова хеш-таблица и да я премине от един стар запис. Тъй като това е много отнемащ време процес, е необходимо да се направи всичко възможно, за да размер на таблицата не се е променило твърде често.
Какво може да замени на хеш таблицата, когато се работи с малки количества от данни?
Можете да използвате Мар (от STL) или двоично дърво. Въпреки, че това изисква O (дневник (п)) време, обем данни не е голяма, така че необходимото време ще бъде малък.
Какво е предимството на карта?
Дървото има поне едно предимство в сравнение с масата на хеш. В сайта можете да се разхождате итератор в възходящ или низходящ ключове и го направи бързо. Hash маса в това отношение се губи.