26 Şubat 2018 Pazartesi

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

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).
Metodun içi şöyle
public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
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
Bu metod null dönebilir. 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.

Ö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
Şö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

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.

// (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;






Hiç yorum yok:

Yorum Gönder