Geek asks and answers

Regarding the implementation of HashMap in java

I tried to do hashmap research and came up with the following analysis:

stack overflow

Q1 Can you guys show me a simple map where you can show the process ... how the hashcode for a given key is calculated in detail using this formula. Compute the position of hash% (arrayLength-1)) where the element should (bucket number), let's say I have hashMap

HashMap map=new HashMap();//HashMap key random order.
         map.put("Amit","Java");
         map.put("Saral","J2EE");

Q2 Sometimes it may happen that the hash codes for two different objects are the same. In this case, 2 objects will be saved in one bucket and will be presented as LinkedList. An entry point is a newly added entity. This object refers to another object of the next field and, therefore, to one. The last entry refers to null. Can you guys show me this with a real example .. !!

.

“Amit” will be allocated to the 10th bucket due to tweedling bit. If there was no twiddeling bit, it would go to the 7th bucket, because 2044535 and 15 = 7. How is this possible, please explain in detail the whole calculation ..?

Updated snapshots ...

enter image description here

and another image ...

enter image description here

+5
source share
4 answers

that the hash code for a given key is calculated in detail using this formula

In the case, Stringthis is calculated using String#hashCode();, which is implemented as follows:

 public int hashCode() {
    int h = hash;
        int len = count;
    if (h == 0 && len > 0) {
        int off = offset;
        char val[] = value;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

Mostly following the equation in java doc

 hashcode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

It is interesting to note that it Stringactually caches its hash code. He can do this because he Stringis immutable.

If I compute the String"Amit" hash code , it will match this integer:

System.out.println("Amit".hashCode());
>     2044535

, , . Java HashMap , 2 ^ n . , , 16, , , 2 ^ 4.

put , - . - , , - ( , ) "" .

, , :

 h & (length-1); // length is the current number of buckets, h the hashcode of the key

, .

"Amit" 10- - -. -twiddeling, 7- , 2044535 & 15 = 7.

, , . , , . , .

HashMap - , , ( , 16 * 0,75 = 12), . Resize 2 * , , , , .

, . , , , , HashMap , .

+2

Q1: hashCode() String

Q2: hashCode() return 1. , - HashMap.

0

, - :

  • - ( , ), , . , "" -.
  • - ( "" ), , - .

, , , , .

0
import java.util.Arrays;
public class Test2 {
public static void main(String[] args) {
    Map<Integer, String> map = new Map<Integer, String>();
    map.put(1, "A");
    map.put(2, "B");
    map.put(3, "C");
    map.put(4, "D");
    map.put(5, "E");

    System.out.println("Iterate");
    for (int i = 0; i < map.size(); i++) {

        System.out.println(map.values()[i].getKey() + " : " + map.values()[i].getValue());
    }

    System.out.println("Get-> 3");
    System.out.println(map.get(3));

    System.out.println("Delete-> 3");
    map.delete(3);

    System.out.println("Iterate again");
    for (int i = 0; i < map.size(); i++) {

        System.out.println(map.values()[i].getKey() + " : " + map.values()[i].getValue());
    }
}

}

class Map<K, V> {

private int size;
private Entry<K, V>[] entries = new Entry[16];

public void put(K key, V value) {

    boolean flag = true;
    for (int i = 0; i < size; i++) {

        if (entries[i].getKey().equals(key)) {
            entries[i].setValue(value);
            flag = false;
            break;
        }
    }

    if (flag) {
        this.ensureCapacity();
        entries[size++] = new Entry<K, V>(key, value);
    }
}

public V get(K key) {

    V value = null;

    for (int i = 0; i < size; i++) {

        if (entries[i].getKey().equals(key)) {
            value = entries[i].getValue();
            break;
        }
    }
    return value;
}

public boolean delete(K key) {
    boolean flag = false;
    Entry<K, V>[] entry = new Entry[size];
    int j = 0;
    int total = size;
    for (int i = 0; i < total; i++) {

        if (!entries[i].getKey().equals(key)) {
            entry[j++] = entries[i];
        } else {
            flag = true;
            size--;
        }
    }

    entries = flag ? entry : entries;
    return flag;
}

public int size() {
    return size;
}

public Entry<K, V>[] values() {
    return entries;
}

private void ensureCapacity() {

    if (size == entries.length) {
        entries = Arrays.copyOf(entries, size * 2);
    }
}

@SuppressWarnings("hiding")
public class Entry<K, V> {

    private K key;
    private V value;

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Entry(K key, V value) {
        super();
        this.key = key;
        this.value = value;
    }

}
}
-1

More articles:


All Articles