Хэш-таблицы VS ассоциативные массивы

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

Ответ 1

В PHP ассоциативные массивы реализованы как hashtables, с немного дополнительной функциональностью.

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

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

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

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

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

$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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

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