Хеш-таблицы ассоциативные массивы VS
Недавно я считал о хеш-таблицах в очень известной книге "Введение в Алгоритмы". Я еще не использовал их ни в каких реальных приложениях, но хочу. Но я не знаю, как запустить.
Кто-либо может дать мне некоторые образцы использования его, например, как понять приложение словаря (как ABBYY Lingvo) использование хеш-таблиц?
И наконец я хотел бы знать то, что различие между хеш-таблицами и ассоциативными массивами в PHP, я имею в виду, какую технологию я должен использовать и в который ситуации?
Если я неправ (я прошу прощения), исправьте меня, потому что на самом деле я запускаю с хеш-таблиц, и у меня есть просто основное (теоретическое) знание о них.
Большое спасибо.
4 ответа
В 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).
Разница между ассоциативным массивом и хеш-таблицей состоит в том, что ассоциативный массив является типом данных, а хеш-таблица - реализацией данных. Очевидно, что тип ассоциативного массива очень важен во многих современных языках программирования: Perl, Python, PHP и т. Д. Хеш-таблица - это основной способ реализации ассоциативного массива, но не совсем единственный. А ассоциативные массивы - это основное, но не единственное применение хеш-таблиц. Так что дело не в том, что они одинаковы, но если у вас уже есть ассоциативные массивы, вам обычно не стоит беспокоиться о разнице.
По соображениям производительности может быть важно знать, что ваши ассоциативные массивы на вашем любимом языке реализованы в виде хэшей. И может быть важно иметь некоторое представление о накладных расходах на эту реализацию. Хеш-таблицы медленнее и используют больше памяти, чем линейные массивы, как вы видите в C.
Perl объединяет эти две концепции вместе, называя ассоциативные массивы «хешами». Как и многие другие возможности Perl, в этом нет ничего плохого, но это небрежно.
Ассоциативный массив - это массив, в котором доступ к элементам осуществляется не по индексу, а по ключу. То, как это работает внутри, зависит от реализации (нет правила, как это должно работать). Ассоциативный массив может быть реализован в виде хэш-таблицы (большинство реализаций так и делают), но он также может быть реализован в виде какой-то древовидной структуры или списка пропусков, или алгоритм просто перебирает все элементы массива и ищет подходящий ключ (это будет ужасно медленно, но это работает).
Хеш-таблица - это способ хранения данных, в котором значения связаны с ключами, и в котором вы собираетесь находить значения для ключей в течение (обычно почти) постоянного времени. Это звучит точно так же, как то, что вы ожидаете от ассоциативного массива, поэтому в большинстве случаев хэш-таблицы используются для реализации таких массивов, но это не обязательно.