Как работают Hashmaps, Treemaps и LinkedHashmaps на Java?

Question

У меня есть различные вопросы, касающиеся карт:

1. Когда итерация в HashMap, не будет никакой гарантии о порядке итерации. Теперь почему?
2. Почему хэш-карты быстрее, чем Treemaps?
3. Как работают LinkedHashMaps, как они поддерживают заказ? Это потому, что у них есть дважды связанный список, содержащий информацию о том, какая запись хранится до и после записи?

Я читал документ API, но поскольку я начинаю заниматься программированием, у меня возникли проблемы с его пониманием.

Answer 1

Когда итерация в HashMap, не будет никакой гарантии о порядке итерации. Теперь почему?

Они вставлены не в порядке их возникновения, но какое значение они имеют.

Например, предположим, что у нас есть хеш-функция h (x), которая возвращает 127 для строки «Hello» и 12 для «Zebra». Если мы вводим эти ключи в нашу хэш-карту, порядок, в котором они считываются, - это «Zebra» -> (независимо от значения), затем «Hello» -> (любое значение прилагается).

Это проявляется в исходном коде для HashMap:

public V put(K key, V value) { 
    return putVal(hash(key), key, value, false, true); 
} 

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

Почему Hashmaps быстрее Treemaps?

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

Есть лот подробнее к источнику для метод.

public V put(K key, V value) { 
    Entry<K,V> t = root; 
    if (t == null) { 
     compare(key, key); // type (and possibly null) check 

     root = new Entry<>(key, value, null); 
     size = 1; 
     modCount++; 
     return null; 
    } 
    int cmp; 
    Entry<K,V> parent; 
    // split comparator and comparable paths 
    Comparator<? super K> cpr = comparator; 
    if (cpr != null) { 
     do { 
      parent = t; 
      cmp = cpr.compare(key, t.key); 
      if (cmp < 0) 
       t = t.left; 
      else if (cmp > 0) 
       t = t.right; 
      else 
       return t.setValue(value); 
     } while (t != null); 
    } 
    else { 
     if (key == null) 
      throw new NullPointerException(); 
     @SuppressWarnings("unchecked") 
      Comparable<? super K> k = (Comparable<? super K>) key; 
     do { 
      parent = t; 
      cmp = k.compareTo(t.key); 
      if (cmp < 0) 
       t = t.left; 
      else if (cmp > 0) 
       t = t.right; 
      else 
       return t.setValue(value); 
     } while (t != null); 
    } 
    Entry<K,V> e = new Entry<>(key, value, parent); 
    if (cmp < 0) 
     parent.left = e; 
    else 
     parent.right = e; 
    fixAfterInsertion(e); 
    size++; 
    modCount++; 
    return null; 
} 

Как работают LinkedHashMaps, как они поддерживают порядок? Это потому, что у них есть дважды связанный список, содержащий информацию о том, какая запись хранится до и после записи?

You can read the source for yourself, но основной вынос здесь:

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

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

Answer 2

Короче говоря: Карты и наборы обычно представляют собой несортированные структуры данных. Если вы хотите «отсортированные наборы», вам, вероятно, лучше использовать списки или массивы.

Ваш вопрос скорее о структурах данных, а не о конкретной конкретной или связанной с Java проблеме программирования, следовательно, вы должны начать с чтения о thoses. (извините, чтобы получить возможность отправлять в ответ: комментирование вопросы необходимо 50 РЭП)