Хэш-таблицы против ассоциативных массивов

Question

Хэш-таблицы против ассоциативных массивов

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

Может ли кто-нибудь дать мне некоторые примеры его использования, например, как реализовать приложение словаря (например, ABBYY Lingvo) с использованием хэш-таблиц?

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

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

Большое спасибо.

845 5

PHP associative-array hashtable

5 ответов:

Comments

Ничего не найдено.

Cam · Accepted Answer · 2017-12-06 01:56:47

в 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).

Sergey Eremin · Accepted Answer · 2010-06-28 19:39:21

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

Greg Kuperberg · Accepted Answer · 2010-06-28 20:36:53

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

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

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

WoZ · Accepted Answer · 2012-03-13 10:57:26

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

Mecki · Accepted Answer · 2010-06-28 20:19:50

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

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