HashMap Sınıfı

Giriş
Şu satırı dahil ederiz.

import java.util.HashMap;

Java'da bir sürü map çeşidi var. Bazıları şöyle

HashTable
ConcurrentHashMap,
Collections.synchronizedMap,
IdentityHashMap,
EnumMap,
WeakHashMap,
LinkedHashMap,
ConcurrentSkipListMap,
TreeMap

Null Key

HashMap Null key değerini kabul eder. Bu değeri 0 numaralı bucket'a koyar

Bucket

Açıklaması şöyle

Before java 8, singly-linked lists were used for storing the nodes. But this implementation has changed to self-balancing BST after a thresold is crossed (static final int TREEIFY_THRESHOLD = 8;).

Yani 8 value nesnesine kadar şöyle

Daha sonra şöyle oluyor

constructor
Şöyle yaparız.

Map<String, Long> map = new HashMap<>();

Varsayalın loadfactor değeri 0.75'tir. Açıklaması şöyle.

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).

Açıklaması şöyle.

The default Load Factor is 0.75, i.e. 3/4, which means that the internal hash table will be resized when 75 of the 100 values have been added.

Metodun içi şöyle.

public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

Çoğu veri yapısı için varsayılan kapasite şöyle.

1. Vector = 10
2. ArrayList = 10
3. LinkedList - does not have a capacity
4. HashMap = 16 (but with the default load factor of 0.75, only 12 can be populated
    before a resize will happen)
5. LinkedHashMap = 16 (read above)  
6. CHM = 16
7. HashSet = 16 (it's  based on a HashMap)
8. LinedHashSet = 16
9. TreeSet = does not have one

constructor - capacity + load factor
Şöyle yaparız.

//Initial capacity is 2 and load factor 75%
HashMap<Foo,String> hashMap=new HashMap<>(2,0.75f);

computeIfPresent metodu
İmzası şöyle.

public V computeIfPresent(K key,
        BiFunction<? super K, ? super V, ? extends V> remappingFunction);

containsKey metodu
Örnek ver

containsValue metodu
Value nesnesi için equals ve hashCode() metodlarını gerçekleştirmek gerekir.
Örnek
Elimizde şöyle bir map olsun

Map<Integer, Person> map = new HashMap<>(); 

Value ile arama yapmak için şöyle yaparız.

boolean test = map.containsValue(new Person(...));

entrySet metodu
Şöyle yaparız.

Map<String, Integer> hashMap = new HashMap<>();
...
Set<Map.Entry<String, Integer>> set = hashMap.entrySet();

for (Map.Entry<String, Integer> me : set) {
  System.out.print(me.getKey() + ": ");
  System.out.println(me.getValue());
}

get metodu
Metodun imzası şöyle. put() metodunun aksine generic değil yani template kullanmıyor. Bu metod null dönebilir.

V get(Object key)

Metodun içi şöyledir.

public V get(Object key)  {
  if (key == null)
    return getForNullKey();
  int hash = hash(key.hashCode());
  for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
  {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
      return e.value;
  }
  return null;
}

Örnek

String k = ...;
Long value = map.get(k);

Örnek
Elimizde şöyle bir kod olsun.

HashMap<String, String> map =...;

Şöyle yaparız.

if(map.get("model")!=null && !map.get("model").isEmpty()){
  //some logic
}

getOrDefault metodu
Value String ise şöyle yaparız.

if (!map.getOrDefault("model", "").isEmpty()) {
    ...
}

merge metodu
Map arayüzünden gelir. Açıklaması şöyle.

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function

Açıklaması şöyle.

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally

Key değeri yok ise ikinci parametreyi çağırır ve sonucunu value olarak atar, var ise üçüncü parametredeki metodu çağırır.

merge() altta compute() metodunu çağırıyor sanırım. Yani merge() yerine compute() çağrılabilir. Şöyle yaparız.

int newValue = hashMap.compute(ch, 
      (key, existingVal) -> (existingVal == null) ? 1 : existingVal + 1);

Örnek
Eskiden şöyle yapardık.

if(hashMap.containsKey(ch)){
    hashMap.replace(ch, 1+hashMap.get(ch));    
}
else{
    hashMap.put(ch, 1);    
}

Şimdi şöyle yaparız.

hashMap.merge(ch, 1, (left, right) -> left + right);

Şöyle yaparız.

hashMap.merge(ch, 1, Math::addExact);

Örnek
Şöyle yaparız.

map.merge("counter", 1, Integer::sum);

Örnek
Bir dizi nesne hakkında istatistik toplamak isteyelim. Şu sql ile aynıdır.

Select sum(paidAmount), count(paidAmount), classificationName,
From tableA
Group by classificationName;

Sonuç şöyledir.

100, 2, classname1 
50, 1, classname2
150, 3, classname3

Şöyle yaparız.

Map<String, Statistics> result = new HashMap<>();
lineItemList.forEach(b -> 
    result.merge(b.getBucketName(), new Statistics(b), Statistics::merge));

put metodu
İmzası şöyle. Eğer key için value varsa yenisi ile yer değiştirir ve eski değeri döner.

public V put(K key, V value);

Metodun içinde döngü var. Şöyledir.

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  Object k;
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
  }
}

Örnek
Şöyle yaparız.

String k = ...;
map.put(k, new Long(10));

putIfAbsent metodu
Örnek
İki tane HashMap'i birleştirmek için kullanılabilir. map1 ve map2 olsun.

HashMap<String, Integer> map1 = ...;
HashMap<String, Integer> map2 = ...;

map2'de olup map1'de olmayanları eklemek için şöyle yaparız.

for (Entry<String,Integer> e : map2) {
  map1.putIfAbsent(e.getkey(),e.getValue());
}

Örnek
Şöyle yaparız.

Map<String, Set<Pair<Integer, Integer>>> map = new HashMap<>();
// ...
map.putIfAbsent(key, new HashSet<>());

Örnek
Şöyle yaparız.

Map<String, List<Pair<Integer, Integer>>> map = new HashMap<>();
// ...
map.putIfAbsent(key, new ArrayList<>());

Diğer
Bucket
Açıklaması şöyle. Eğer bir bucket'a fazla sayıda elemen düşüyorsa o bucket BinaryTree olarak saklanıyor

/*
 * Implementation notes.
 *
 * This map usually acts as a binned (bucketed) hash table, but
 * when bins get too large, they are transformed into bins of
 * TreeNodes, each structured similarly to those in
 * java.util.TreeMap. Most methods try to use normal bins, but
 * relay to TreeNode methods when applicable (simply by checking
 * instanceof a node).  Bins of TreeNodes may be traversed and
 * used like any others, but additionally support faster lookup
 * when overpopulated. However, since the vast majority of bins in
 * normal use are not overpopulated, checking for existence of
 * tree bins may be delayed in the course of table methods.

Bu iş için şöyle sabitler tanımlı. Eğer 8'den fazla nesne olursa tree'ye çevrilir.Eğer nesne sayısı 6'dan küçükse tekrar list'e çevirilir. Eğer bucket sayısı 64'ten küçükse bucket'ları tree'ye çevirmek yerine önce HashMap bucket sayısı büyütülür.

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Bucket düğümü şöyle tanımlı.

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> {
  HashMap.TreeNode<K, V> parent;
  HashMap.TreeNode<K, V> left;
  HashMap.TreeNode<K, V> right;
  HashMap.TreeNode<K, V> prev;
  boolean red;

  TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) {
    super(arg0, arg1, arg2, arg3);
  }

  final HashMap.TreeNode<K, V> root() {
    HashMap.TreeNode arg0 = this;

    while (true) {
      HashMap.TreeNode arg1 = arg0.parent;
      if (arg0.parent == null) {
        return arg0;
      }

      arg0 = arg1;
    }
  }
    //...
}

Key için Hash metodu

Rust dili hash metodu olarak cryptographically secure yöntemler kullanıyor. Açıklaması şöyle

By default, HashMap uses a cryptographically secure hashing function that can provide resistance to Denial of Service (DoS) attacks. This is not the fastest hashing algorithm available, but the trade-off for better security that comes with the drop in performance is worth it.

Java ise kendi hash metodunu kullanıyor. Açıklaması şöyle.

[This method] computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don't benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

Şöyledir.

// (I have restructured the code for ease of comparison.)
 int h;
 hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 index = (tab.length - 1) & hash;