алгоритмы: реализация пользовательских хеш-таблиц на основе dict

Question

Я изучаю программирование абстрактных типов данных. Попытка создать пользовательский хеш-таблицу на основе dict.

Пока я создал заполнитель класса.

    public class HashMapDict implements IDict
{
    private var _map:Array;
    public function HashMapDict()
    {
        _map = new Array();

        //TODO: implement function
    }

    public function set(keys:Array):Boolean
    {
        // 1. For each key in array of keys
        // 2. Pass Key.key to hash function
        // 3. Write Key to _map[hash(Key.key)]
        return true;
    }


}

Я вижу основной набор методов, выполняющий следующее

// 1. For each key in array of keys
// 2. Pass Key.key to hash function
// 3. Write Key to _map[hash(Key.key)]

Я думаю о том, чтобы использовать криптографические библиотеки для генерации хешей. Но я немного запутался с тем, как это должно работать. например Попытался взглянуть на несколько библиотек, таких как as3crypto (http://crypto.hurlant.com/demo/)), и, похоже, он производит хэш способом, который, я не думаю, может использоваться для индексов в массивах.

например.

http://screencast.com/t/bE1lYQEqp4D

Можете ли вы посоветовать, какую библиотеку я могу использовать для создания полезных хешей? и как они должны выглядеть

Answer 1

Точно так же, как один на один - я почти гарантирую, что вы не сможете сделать что-то лучше, чем Dictionary или даже Object в этом. Ваш предложенный план может сработать, но он не даст никакой выгоды по сравнению с этим. Я также чувствую себя обязанным предложить Vector over Array, поскольку векторы быстрее и мощнее.

Проблема хеш-библиотек в том, что они обычно приводят к очень, очень большому количеству. Например, MD5 создаст шестнадцатеричную строку, которая представляет собой гораздо больше, чем то, что может поместиться даже в uint (в uint можно указать 2 ^ 32, MD5 - 2 ^ 128). Это также может быть максимальный размер массива / вектора в AS.

Это не означает, что они не могут вписаться в Number (который может содержать около 1,79 * 10 ^ 308), но это означает, что вы потеряете преимущество числовой индексации и, безусловно, выиграете ». На этом этапе у Векторов нет большой пользы. Вы в основном будете отступать на Object.

Если честно, похоже, у вас есть один из двух вариантов. Либо вы можете реализовать прямой поиск, используя второй массив / вектор. Проблема состоит в том, что O (n) время поиска, в то время как время поиска таблицы Hash будет O (1).

Кажется, по крайней мере мне, что вам нужно будет использовать Dictionary или Object независимо от того, что для этого нужно сделать.

Answer 2

Для реализации хеш-таблицы криптографическая хеш-функция является избыточной.

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

Для использования хеш-таблицы достаточно хэш-функции, подобной следующей (псевдокод, поскольку я не знаю правильный синтаксис):

hash = 0
for c in string:
   hash = hash * 13 + c;
return hash   

Но, как уже говорили другие ответы, встроенная хеш-таблица уже существует, и вам не нужно ее переопределять.

Answer 3

Я мог бы что-то упустить, но я думаю, вы должны посмотреть на flash.utils::Dictionary.
Это делает хеширование устаревшим. Если вы должны иметь какой-то примитивный ключ, я предлагаю использовать следующее:

class UIDUtil {
    static private var map:Dictionary = new Dictionary(true);
    static private var counter:int = 0;
    static public function getUID(value:*):int {
         return map[value] ||= counter++;
    }
}

Но твой класс я бы реализовал так:

public class HashMapDict implements IDict {
    private var _map:Dictionary = new Dictionary();
    public function set(keys:Array):Boolean {
        for each (var key:* in keys) _map[key] = key;
        return true;
    }
}

Хотя я не уверен в его назначении;)