Хеш-таблицы VS ассоциативных массивов - PullRequest
79 голосов
/ 28 июня 2010

Недавно я прочитал о хеш-таблицах в очень известной книге " Введение в алгоритмы ". Я еще не использовал их в реальных приложениях, но хочу. Но я не знаю с чего начать.
Кто-нибудь может дать мне несколько примеров его использования, например, как реализовать приложение-словарь (например, ABBYY Lingvo) с использованием хеш-таблиц?
И, наконец, я хотел бы знать, в чем разница между хеш-таблицами и ассоциативными массивами в PHP, я имею в виду, какую технологию использовать и в каких ситуациях?
Если я ошибаюсь (прошу прощения), пожалуйста, поправьте меня, потому что на самом деле я начинаю с хеш-таблиц, и у меня есть только базовые (теоретические) знания о них.
Большое спасибо.

Ответы [ 5 ]

118 голосов
/ 28 июня 2010

В PHP ассоциативные массивы реализованы в виде хеш-таблиц с небольшой дополнительной функциональностью.

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

Например, вы можете перебирать ассоциативный массив с помощью цикла for, который вы можете 'Это невозможно сделать с хеш-таблицей.

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

Примеры кода:

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

$favoriteColor = array();
$favoriteColor['bob']='blue';
$favoriteColor['Peter']='red';
$favoriteColor['Sally']='pink';
echo 'bob likes: '.$favoriteColor['bob']."\n";
echo 'Sally likes: '.$favoriteColor['Sally']."\n";
//output: bob likes blue
//        Sally likes pink

Цикл по ассоциативному массиву :

$idTable=array();
$idTable['Tyler']=1;
$idTable['Bill']=20;
$idTable['Marc']=4;
//up until here, we're using the array as a hashtable.

//now we loop through the array - you can't do this with a hashtable:
foreach($idTable as $person=>$id)
    echo 'id: '.$id.' | person: '.$person."\n";

//output: id: 1 | person: Tyler
//        id: 20 | person: Bill
//        id: 4 | person: Marc

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

21 голосов
/ 28 июня 2010

PHP-массивы в основном хеш-таблицы

16 голосов
/ 28 июня 2010

Разница между ассоциативным массивом и хеш-таблицей заключается в том, что ассоциативный массив является типом данных, в то время как хеш-таблица является реализацией данных. Очевидно, что тип ассоциативного массива очень важен во многих современных языках программирования: Perl, Python, PHP и т. Д. Хеш-таблица является основным способом реализации ассоциативного массива, но не совсем единственным способом. А ассоциативные массивы - это основное использование хеш-таблиц, но не единственное использование. Так что это не значит, что они одинаковы, но если у вас уже есть ассоциативные массивы, вам обычно не стоит беспокоиться о разнице.

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

Perl объединяет два понятия, называя ассоциативные массивы "хешами". Как и ряд функций Perl, это не совсем так, но небрежно.

9 голосов
/ 13 марта 2012

Массив в PHP на самом деле является упорядоченной картой, а не хеш-таблицей. Основное различие между картой и хэш-таблицей заключается в невозможности запомнить порядок добавления элементов. С другой стороны, хеш-таблицы намного быстрее, чем карты. Сложность извлечения элемента из карты - O (nlogn), а из хеш-таблицы - O (1).

2 голосов
/ 28 июня 2010

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

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

...