Study of several Map- Java of just how far we can go. Series (27)

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Just how far we can go. Series(27)

Bullshit.:

Your job now is the process of personal growth.?

You can directly to a large number of just interested in working in middle school?

Are your hobbies in his spare time to study it?

You work overtime, whether the time has affected your interest in learning programming?


Theme:

Hashtable Provides an easy to use, thread safe map function, Hashtable  in all operating methods are synchronized, so performance compared with non thread safe HashMap fell. The structure is similar, the first one array, each deposit linked list array.

As shown in Fig.:

This is their data structure. some source code:

Constructor:

    public Hashtable( int initialCapacity, float loadFactor) {
        if (initialCapacity <= 0) initialCapacity = 11;
        if (loadFactor <= 0.0) loadFactor = 0.75f;
        this.loadFactor = loadFactor;
        table = new HashtableEntry[initialCapacity];
        threshold = (int )(initialCapacity * loadFactor);
    }

threshold = array (initialCapacity ) * load factor(loadFactor)

So if the initialization of map defines a 100 fan, 75 is the limit.


According to this structure we to have a look to access the data source, we can see some differences between the two.

 

The first is Hashtable :

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        // Hashtable does not support null as key
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length ;
        // As the data in the array, if you already have a value, add to the end of the list type
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e. value;
                e. value = value;
                return old;
            }
        }

        modCount++;
        
        if (count >= threshold ) {
            // Rehash the table if the threshold is exceeded
            // Redefine the array length, re arranged for all hashcode
            rehash();

            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab. length;
        }

        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null ;
    }


public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length ;
        // According to the address data.
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value ;
            }
        }
        return null ;
    }


Below is the HashMap access code:

 public V put(K key, V value) {
          // HashMap supports null as key
        if (key == null )
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table. length);
        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;
            }
        }

        modCount++;
        // Method to open out, to subclass a custom implementation
        addEntry(hash, key, value, i);
        return null ;
    }

    void addEntry( int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold ) && (null != table[bucketIndex])) {
            // Expand 2 times
            resize(2 * table. length);
            hash = ( null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    public V get(Object key) {
        if (key == null )
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();// Method to open out
    }

    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        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 != null && key.equals(k))))
                return e;
        }
        return null ;
    }


Some understanding:

1, From the above code to see the structure of map is basically the same, we will pay attention to, if the inserted data when these data, the average allocation to the array, that is to say the data structure produced no list, then the data through the address query, if the worst case, that is the most or all of the data in hashcode are the same, lead to all the data in a linked list structure array subscript under, so this list will become very big, so every time the query is worst traversal queries, will lose the significance of map.

So at the time of operation, number of elements in the list, efficiency is low, because to keep the list of cycle comparison. So, must hash evenly distributed, minimize hash collision, reducing the hash collision, reducing the chain cycle, improve efficiency.

This problem is to do a cause: Hash Collision DoS

From the       http://coolshell.cn/articles/6424.html  description:

Whether you use JSP, PHP, Python, Ruby to write the webpage, when processing the HTTP POST data, your daemon can easily to access the form field names to access the form values, like this program.:

1

2

$usrname = $_POST['username'];

$passwd = $_POST['password'];

How is this possible? This is a Hash Map back, So, I can give you the background to submit a 10K field form, These fields are I carefully design., They are all Hash  Collision , So your Web Server or language processing this form when, The hash map will be built, So when each into a form field, Can first traversal over you all plugged field, So your server's CPU 100%, You'll find this 10K nothing, Then I will send a request, Your server will not work.

For example, you may be more easy to understand:

If you have a n value of — — V1, V2, V3, … VN, put them into the hash table should be enough hashing, such that high performance:

0 -> v2
1 -> v4
2 -> v1


n -> v(x)

However, this attack can let me make N a value of — —   dos1, dos2, … dosn, hash. Key, they are the same (or Hash Collision), result in your hash table became like the following:

0 – > dos1 -> dos2 -> dos3 -> …. ->dosn
1 -> null
2 -> null


n -> null

So, a one-way link appeared so. Thus, O (1) search algorithm complexity is O (n), and insert the N data of the complexity of the algorithm is O (n^2), do you think this is what kind of performance.


2, Also note, array in map is of length, when put in enough data, is to satisfy the

Hashtable   count  > =  threshold (threshold had mentioned above)

HashMap size >= threshold

Causes the Hashtable execute rehash (), HashMap will execute resize(2 * table. length)

The two method is very time consuming, because they want to calculate hashcode for each data, recalculate the position in the array.

 

On the resize problem:



About LinkedHashMap:


Sometimes when the achievement of business we need an ordered Map, may think of LinkedHashMap

The fact that it inherits from HashMap, he maintains a two-way linked list, in order to save the data sequence.

Look at his increased data method:

     void addEntry( int hash, K key, V value, int bucketIndex) {
        super .addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header. after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest. key);
        }
    }

The addEntry method is invoked in the put public method in hashMap (front source mentioned), first class code and its realizing method is to maintain the order of words, which, in the list so, when to take out can be more this list obtained sequence data.





Let us move on

----------------------------------------------------------------------

Efforts may not succeed, but do not work hard will not succeed.
Share.


Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by 007 at November 15, 2013 - 3:39 AM