Hash_map автоматически сортирует [C ++]?

Question

В приведенном ниже коде hash_map автоматически сортирует или, возможно, вставляет элементы в отсортированном порядке.Есть идеи, почему он это делает?Предложения, пожалуйста ??Это НЕ домашняя проблема, пытаясь решить вопрос об интервью, опубликованном на glassdoor dot com.

#include <iostream>
#include <vector>
#include <ext/hash_map>
#include <map>
#include <string.h>
#include <sstream>

using namespace __gnu_cxx;
using namespace std;

struct eqstr
{
  bool operator()(int i, int j) const
  {
    return i==j;
  }
};
typedef hash_map<int, int, hash<int>, eqstr> myHash;
int main()
{
    myHash array;
    int inputArr[20] = {1,43,4,5,6,17,12,163,15,16,7,18,19,20,122,124,125,126,128,100};

    for(int i=0;i<20;i++){
        array[inputArr[i]] = inputArr[i]; //save value
    }
    myHash::iterator it = array.begin();
    int data;
    for (; it != array.end(); ++it) {
        data =  it->first;
        cout << ":: " << data;
    }
}

//!Output ::: 1:: 4:: 5:: 6:: 7:: 12:: 15:: 16:: 17:: 18:: 19:: 20:: 43:: 100:: 122:: 124:: 125:: 126:: 128:: 163

Answer 1

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

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

Пример чистого счетчика можно создать, заменив эти 100 на 999999999. В результате получается

:: 1:: 4:: 5:: 6:: 7:: 12:: 15:: 16:: 17:: 18:: 19:: 20:: 999999999:: 43:: 122:: 124:: 125:: 126:: 128:: 163

---

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

Answer 2

Хеш-карта может отображаться для сортировки по нескольким факторам:

• Хеш-функция возвращает значения в том же порядке, что и ввод, для диапазона вводимых вами данных.
• Нет коллизий хешей.

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

Answer 3

Подумайте, как работает хеш-функция. Хеш - это всегда функция f: input-> output , которая отображает входной набор I в (обычно меньший) выходной набор O, так что входной набор приблизительно равномерно распределен по выходному набору.

Нет требования , что порядок должен быть сохранен; фактически, это необычно, что это будет сохранено, потому что (поскольку выходной набор меньше), будут значения * i, j *, которые имеют одинаковый хэш. Это называется столкновением .

С другой стороны, нет причин, по которым это не следует. Фактически, можно доказать, что всегда будет существовать хотя бы одна последовательность, в которой будет сохранять порядок.

Но есть и другая возможность: если ВСЕ значения сталкиваются, то они сохраняются в какой-то другой структуре данных, например в списке. Может случиться так, что все они сталкиваются, а другая структура навязывает порядок.

Три возможности: hash_map случается, чтобы отсортировать эту конкретную последовательность, или hash_map фактически реализуется как массив, или значения сталкиваются, и реализация сохраняет коллизии таким образом, что дает отсортированный порядок.