进修java中的几个Map-我们到底能走多远系列（27）

    添加时间:2013-5-23 点击量:

    我们到底能走多远系列（27）


    扯淡：


    你如今的工作过程是否利于小我成长呢？


    你能直接在工作中学到多量刚爱好的器材吗？


    你的爱好都是在业余时候进修的吗？


    你加班的时候是否已经影响了你对编程进修的爱好？



    主题：


    Hashtable 供给了一种易于应用的、线程安然的map功能，Hashtable 中所有操纵办法都是同步的，所以机能较于非线程安然的HashMap就降落了。两者的布局差不久不多，先有一个数组，数组的每一位存链表。

    如图：



    这就是他们的数据布局啦。看一些源码：


    机关函数：



        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 = 数组局限（initialCapacity ） 装载因子（loadFactor）

    所以若是初始化map的时辰限制100的范，那么75就是界线。

     



    按照这个布局我们来看看存取数据的源码，可以看出两者之间的一些差别。

     

    起首是Hashtable 的：



    public synchronized V put（K key， V value） {

                // Make sure the value is not null

                // Hashtable 不支撑null作为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 & 0 x7FFFFFFF） ％ tab.length ;

                // 像数组中放数据，若是已经有值，则以链表的型式参加末尾

            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

                    // 从头定义数组长度，对所有的hashcode进行从头设置

                rehash（）;

    

                tab     = table;

                hash     = hash（key）;

                index     = （hash & 0 x7FFFFFFF） ％ 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 & 0 x7FFFFFFF） ％ tab.length ;

                // 按照下标地址查询数据

            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 ;

        }



    下面是HashMap的存取源码：






     public V put（K key， V value） {

                  // HashMap 支撑null作为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    ++;

                // 拆出去的办法，利于子类的自定义实现

            addEntry（hash， key， value， i）;

                return null ;

        }

    

            void addEntry（ int hash， K key， V value， int bucketIndex） {

                if （（size >= threshold ） && （null != table[bucketIndex]）） {

                    // 扩大2倍

                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（）;// 拆出去的办法

        }

    

            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 ;

        }



    一些懂得：


    1，从上方的代码看map的布局基同，我们会重视到，若是在插入数据的时辰，这些数据均匀的分派到数组上，也就是说没有产生链表的数据布局，那么在取得这个数据是经由过程地址查询的，若是呈现最坏的景象，那就是大多或所有的数据的hashcode都雷同，导致所有的数据都存在某个数组下标下的链表布局上，那么这个链表会变得很大，如此每次查询最坏的是遍历查询，也就落空的map的意义。



    所以在操纵的时辰，链表中的元素越多，效力越低，因为要不绝的对链表轮回斗劲。所以，必然要哈希均匀分布，尽量削减哈希冲突，削减了哈希冲突，就削减了链表轮回，就进步了效力。

    这个题目就肯呢过会引起：Hash Collision DoS

    来自   http://coolshell.cn/articles/6424.html  的描述:



    无论你用JSP，PHP，Python，Ruby来写后台网页的时辰，在处理惩罚HTTP POST数据的时辰，你的后台法度可以很轻易地以接见表单字段名来接见表单值，就像下面这段法度一样：








    1

    2

    分享到：