精华内容
下载资源
问答
  • Hashtable扩容,源码阅读

    2021-02-24 16:48:20
    这篇文章,是笔者学习hash源码的笔记,写作的过程,利于...这是第一篇,讲解hashtable扩容。虽然hashtable已经被ConcurrentHashMap取代了,但是源码简单,利于我们理解hash的实现方式。 先看hashtable的结构图 ...

    这篇文章,是笔者学习hash源码的笔记,写作的过程,利于知识梳理,找到盲区。将会分三篇文章。
    这是第一篇,讲解hashtable扩容。虽然hashtable已经被ConcurrentHashMap取代了,但是源码简单,利于我们理解hash的实现方式。

    先看hashtable的结构图


    hashtable表结构。数组+元素节点是单链表。

    默认数组长度是11,负载因子是0.75

     /**
         * Constructs a new, empty hashtable with a default initial capacity (11)
         * and load factor (0.75).
         */
        public Hashtable() {
            this(11, 0.75f);
        }
    

    可以手动指定。为什么hashMap的初始化是16,hashtable是11?原因是hashmap做了优化,后面hashMap篇讲解。

    HashTable扩容,元素数量达到阈值。阈值的计算。数组长度 * 负载因子

    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    

    默认的hashtable,当插入第9个元素时候,会扩容。测试代码如下

    public class HashTableTest {
    
        public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
            Hashtable<String, Integer> table = new Hashtable<>();
            table.put("0", 112);
            table.put("1", 1);
            table.put("2", 1);
            table.put("3", 1);
            table.put("4", 1);
            table.put("5", 1);
            table.put("6", 1);
            table.put("7", 1);
    //        table.put("8", 1);
            log.info("" + ((Map.Entry[])(getValue(Hashtable.class, table, "table"))).length);
            int c = (int)Math.min(11f * 0.75f, 100.0f);
            log.info("" + c);
        }
    
        private static Object getValue(Class c1, Object o, String field) throws NoSuchFieldException, IllegalAccessException {
            Field field1 = c1.getDeclaredField(field);
            field1.setAccessible(true);
            return field1.get(o);
        }
    }
    
    18:00:55.288 [main] INFO com.austin.daily.hashMap.HashTableTest - 11
    
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
            Hashtable<String, Integer> table = new Hashtable<>();
            table.put("0", 112);
            table.put("1", 1);
            table.put("2", 1);
            table.put("3", 1);
            table.put("4", 1);
            table.put("5", 1);
            table.put("6", 1);
            table.put("7", 1);
            table.put("8", 1);
            log.info("" + ((Map.Entry[])(getValue(Hashtable.class, table, "table"))).length);
        }
    INFO com.austin.daily.hashMap.HashTableTest - 23
    

    扩容规则是什么呢?

    private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            if (count >= threshold) {
                // Rehash the table if the threshold is exceeded
                rehash();
    
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // Creates the new entry.
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }
    

    添加Entry前,先判断达到threshold,核心代码在rehash()

    protected void rehash() {
    		//记录原有hash表的长度
            int oldCapacity = table.length;
            //追踪引用原有hash表对象
            Entry<?,?>[] oldMap = table;
    
            // overflow-conscious code
            //计算新数组长度,old乘以2 +1. 所以 11 * 2 +1 = 23
            int newCapacity = (oldCapacity << 1) + 1;
            //防止超过JVM规定的数组最大长度
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                if (oldCapacity == MAX_ARRAY_SIZE)
                    // Keep running with MAX_ARRAY_SIZE buckets
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            //创建一个新hash数组
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    		//与并发操作锁有关系,待后续了解
            modCount++;
            //计算新的阈值
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            //替换为新的数组
            table = newMap;
    		//核心中的核心   循环old hash表的所有element(element是单链表的head)
            for (int i = oldCapacity ; i-- > 0 ;) {
            	//利用单链表的特性,循环到链尾
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                	//记录当前element
                    Entry<K,V> e = old;
                    //下一次循环用当前元素的next
                    old = old.next;
    				//计算element的hashcode,将正负位转为0,保证是正数,再取模,得到新hash表的索引位置
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                    //两行要理清楚。当前element的next指向该索引的值。目的是当前元素成为该索引下单链表的head。经过循环,当前element都会作为head插入到单链表中。头插法
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }
    

    每行代码都有注释。至此。已经解析完扩容机制。

    我注意到。put()方法是头插法,rehash()也是头插法。会导致rehash后,插入顺序会逆转。下面是代码验证

    @Slf4j
    public class HashTableTest {
    
        public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
    //        Hashtable<String, Integer> table = new Hashtable<>();
    //        table.put("0", 112);
    //        table.put("1", 1);
    //        table.put("2", 1);
    //        table.put("3", 1);
    //        table.put("4", 1);
    //        table.put("5", 1);
    //        table.put("6", 1);
    //        table.put("7", 1);
    //        table.put("8", 1);
    //        log.info("" + ((Map.Entry[])(getValue(Hashtable.class, table, "table"))).length);
    //        int c = (int)Math.min(11f * 0.75f, 100.0f);
    //        log.info("" + c);
    
            Hashtable<Kk, Integer> table = new Hashtable<>();
            table.put(new Kk(), 0);
            table.put(new Kk(), 1);
            table.put(new Kk(), 2);
            table.put(new Kk(), 3);
            table.put(new Kk(), 4);
            table.put(new Kk(), 5);
            table.put(new Kk(), 6);
            table.put(new Kk(), 7);
    //        table.put(new Kk(), 8);
    
            Map.Entry[] entries = (Map.Entry[])getValue(Hashtable.class, table, "table");
            Map.Entry entry = entries[1];
            while (entry != null) {
                System.out.print(getValue(entry.getClass(), entry, "value") + ",");
                entry = (Map.Entry)getValue(entry.getClass(), entry, "next");
            }
            System.out.println("");
            System.out.println("扩容后");
            //扩容后
            table.put(new Kk(), 8);
            entries = (Map.Entry[])getValue(Hashtable.class, table, "table");
            entry = entries[1];
            while (entry != null) {
                System.out.print(getValue(entry.getClass(), entry, "value") + ",");
                entry = (Map.Entry)getValue(entry.getClass(), entry, "next");
            }
        }
    
        private static Object getValue(Class c1, Object o, String field) throws NoSuchFieldException, IllegalAccessException {
            Field field1 = c1.getDeclaredField(field);
            field1.setAccessible(true);
            return field1.get(o);
        }
    }
    
    class Kk {
    
        @Override
        public int hashCode() {
            return 1;
        }
    }
    
    7,6,5,4,3,2,1,0,
    扩容后
    8,0,1,2,3,4,5,6,7,
    Process finished with exit code 0
    

    创建类Kk,覆盖hashCode,使得element一定会在数组索引1。打印的是table[1]的单链表元素顺序。
    观察扩容前,头插法,所以在前面;
    扩容中,验证后,果然是和倒置插入顺序。8在最前面的原因是,会先处理原有element,再使用头插法。

    展开全文
  • 必知必会--Hashtable扩容机制

    千次阅读 2019-09-16 14:07:46
    Hashtable扩容机制通过rehash()来实现,如果Hashtable中元素的个数大于临界值时,会调用rehash()来实现扩容。临界值的大小等于Hashtable数组的大小与负载因子相乘,默认的负载因子大小为0.75。 protected void ...

    阅读源码时,在Hashtable的扩容看到几个有意思的点。

    正文

    Hashtable的扩容机制通过rehash()来实现,如果Hashtable中元素的个数大于临界值时,会调用rehash()来实现扩容。临界值的大小等于Hashtable数组的大小与负载因子相乘,默认的负载因子大小为0.75。

    protected void rehash() {
            int oldCapacity = table.length;
            Entry<?,?>[] oldMap = table;
    
            // 新数组的容量=旧数组长度*2+1
            int newCapacity = (oldCapacity << 1) + 1;
            // 保证新数组的大小永远小于等于MAX_ARRAY_SIZE
            // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                if (oldCapacity == MAX_ARRAY_SIZE)
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            // 创建新数组
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
            modCount++;
            // 计算新的临界值
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;
    
            // 将旧数组中的元素迁移到新数组中
            for (int i = oldCapacity ; i-- > 0 ;) {
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                    Entry<K,V> e = old;
                    old = old.next;
    
                    //计算新数组下标
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                    // 头插法的方式迁移旧数组的元素
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }

    Hashtable扩容的数组长度是旧数组长度乘以2加1

    Hashtable采用取模的方式来计算数组下标,同时数组的长度尽量为素数或者奇数,这样的目的是为了减少Hash碰撞,计算出来的数组下标更加分散,让元素均匀的分布在数组各个位置。

    采用模运算效率会比HashMap利用位运算计算数组下标更低。

    Hashtable采用头插法的方式迁移数组

    与HashMap不同的是。在扩容时Hashtable采用头插法的方式迁移数据,使用头插法效率会更高。因为头插法减少了遍历链表的时间,效率更高。

    虽然rehash()方法没有被synchronized修饰,这并不意味着rehash()方法非线程安全,这是因为所有调用rehash()的方法均被synchronized修饰。

    所以即使HashMap因为线程安全问题在JDK1.8抛弃了头插法而采用高地位平移算法,Hashtable在JDK1.8仍采用头插法迁移元素,因为Hashtable为了线程安全而设计,不会存在HashMap类似的问题。

    Hashtable处于一个比较尴尬的位置,以至于官方也推荐如果不考虑线程安全,建议使用HashMap,如果考虑到同步效率,建议使用ConcurrentHashMap。

    JDk1.8源码--HashMap扩容机制

    展开全文
  • [置顶] Redis2.2.2源码学习——dict中的hashtable扩容和rehash 分类: Redis2013-10-17 13:35 336人阅读 评论(0) 收藏 举报 redishash扩容 Redis2.2.2   dict是Redis的hash数据结构,所有类型...
     

    [置顶] Redis2.2.2源码学习——dict中的hashtable扩容和rehash

    分类: Redis   336人阅读  评论(0)  收藏  举报

    Redis2.2.2 

            dict是Redis的hash数据结构,所有类型的元素都可以依据key值计算hashkey,然后将元素插入到dict的某个hash链上(采用拉链法解决hash冲突)。其中,dict的中的hashtable(dictht)的扩容是dict很重要的部分。Redis的“管家”函数serverCron会依据一定的算法(dict中的used与size的比值)判定是否开始进行hashtable的扩容。dict中的ht[1]是作为扩容的临时数据,扩容之后,hashtalbe的长度将变长,那么hashtalbe的masksize与原来的makssize就不同了,那么计算出的hashkey也将不同。所以就需要Rehash对ht[0]中的元素重新计算hashkey。

            在Rehash阶段,首先将原来的ht[0]中的元素重新rehash到ht[1]中,故而要耗费大量的力气从新计算原来的ht[0]表中元素的在ht[1]表总的hashkey,并将元素转移到ht[1]的表中。由于这样Rehash会耗费大量的系统资源,如果一次性完成一个dict的Rehash工作,那么将会对系统中的其他任务造成延迟? 作者的处理方式是:同样在serverCron中调用rehash相关函数,1ms的时间限定内,调用rehash()函数,每次仅处理少量的转移任务(100个元素)。这样有点类似于操作系统的时间片轮转的调度算法。


    下图是Dict相关数据结构(引用: Redis源码剖析(经典版).docx )



    代码分析如下:

    [cpp]  view plain copy
    1. -----------------------Data Sturcter----------------------------------------  
    2.   
    3. typedef struct dictEntry {  
    4.     void *key;  
    5.     void *val;  //空类型,redis的类型主要有sds,list,set等,val指针指向其中的结构  
    6.     struct dictEntry *next;  
    7. } dictEntry;  
    8.   
    9. typedef struct dictType {  
    10.     unsigned int (*hashFunction)(const void *key);  
    11.     void *(*keyDup)(void *privdata, const void *key);  
    12.     void *(*valDup)(void *privdata, const void *obj);  
    13.     int (*keyCompare)(void *privdata, const void *key1, const void *key2);  
    14.     void (*keyDestructor)(void *privdata, void *key);  
    15.     void (*valDestructor)(void *privdata, void *obj);  
    16. } dictType;  
    17.   
    18. /* This is our hash table structure. Every dictionary has two of this as we 
    19.  * implement incremental rehashing, for the old to the new table. */  
    20. typedef struct dictht {  
    21.     dictEntry **table;//hash表,每个table[i]链表存储着一个hashkey相等的dictEntry指针  
    22.     unsigned long size;//table[]的大小  
    23.     unsigned long sizemask;// = size-1  
    24.     unsigned long used;//当前table中存储的dictEntry指针的个数  
    25. } dictht;  
    26.   
    27. typedef struct dict {  
    28.     dictType *type;//hash相关的操作hander  
    29.     void *privdata;  
    30.     dictht ht[2];//ht[0]作为dict的实际hash结构,ht[1]做为扩容阶段的转储结构  
    31.     int rehashidx; //标志dict是否处于rehash阶段,如果值为-1,表示不处于rehash。否则,在rehash中所谓hashtalbe的索引下标  
    32.     int iterators; /* number of iterators currently running */  
    33. } dict;  
    34.   
    35. ------------------------Redis's main----------------------------------------  
    36.   
    37. main() >   
    38.     initServerConfig()  
    39.         server.activerehashing = 1;  
    40.     initServer()  
    41.         //设置定时事件,1ms调用一次serverCron()  
    42.         aeCreateTimeEvent(server.el, 1, serverCron, NULL, NULL);  
    43.     //进入事件轮询,详见:http://blog.csdn.net/ordeder/article/details/12791359  
    44.     aeMain(server.el)  
    45.   
    46. ------------------------serverCron-----------------------------------------  
    47.   
    48. /*serverCron是Redis的协调员,其中就包括:  
    [cpp]  view plain copy
    1. 1.检查是否有hashtalbe需要扩容,并执行必要的扩容  
    [cpp]  view plain copy
    1. 2.执行incrementRehash执行固定时间的Rehash任务  
    [cpp]  view plain copy
    1. */  
    2. int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData)  
    3.     /*记录sever调用serverCron的总次数 
    4.     *对于需要协调的不同的任务,可以依据loops%n的方式设置不同的频率 */  
    5.     int loops = server.cronloops   
    6.     。。。  
    7.     /* We don't want to resize the hash tables while a bacground saving 
    8.      * is in progress: the saving child is created using fork() that is 
    9.      * implemented with a copy-on-write semantic in most modern systems, so 
    10.      * if we resize the HT while there is the saving child at work actually 
    11.      * a lot of memory movements in the parent will cause a lot of pages 
    12.      * copied. 后台没有对数据进行操作的程序...*/  
    13.     if (server.bgsavechildpid == -1 && server.bgrewritechildpid == -1) {  
    14.         /*loops % 10 :  
    15.         serverCron没循环10次,进行一次tryResizeHashTables检查*/  
    16.         if (!(loops % 10)) tryResizeHashTables();  
    17.             //下面的for是tryResizeHashTables源码  
    18.             >for (j = 0; j < server.dbnum; j++) {  
    19.                 //htNeedsResize:检查used*100/size < REDIS_HT_MINFILL(设定的阈值)  
    20.                 if (htNeedsResize(server.db[j].dict))   
    21.                     dictResize(server.db[j].dict);//见下文分析 扩容Resize  
    22.                 if (htNeedsResize(server.db[j].expires))  
    23.                     dictResize(server.db[j].expires);  
    24.             >}  
    25.         if (server.activerehashing)   
    26.             incrementallyRehash();//见下文分析 Rehash  
    27.     }  
    28.   
    29. ------------------------扩容Resize------------------------------------------  
    30.   
    31. /* Resize the table to the minimal size that contains all the elements, 
    32.  * but with the invariant of a USER/BUCKETS ratio near to <= 1 */  
    33. int dictResize(dict *d)  
    34. {  
    35.     int minimal;  
    36.   
    37.     if (!dict_can_resize || dictIsRehashing(d)/*rehashidx ?= -1*/return DICT_ERR;  
    38.     minimal = d->ht[0].used;  
    39.     if (minimal < DICT_HT_INITIAL_SIZE)  
    40.         minimal = DICT_HT_INITIAL_SIZE;  
    41.     //minimal = Max(d->ht[0].used,DICT_HT_INITIAL_SIZE)  
    42.     //原来的容量为size,现要扩充到used或DICT_HT_INITIAL_SIZE  
    43.     return dictExpand(d, minimal);  
    44. }  
    45.   
    46. /* Expand or create the hashtable */  
    47. int dictExpand(dict *d, unsigned long size)  
    48. {  
    49.     dictht n; /* the new hashtable */  
    50.     //将size扩展到2^n : while(1) { if (i >= size) return i; i *= 2; }  
    51.     unsigned long realsize = _dictNextPower(size);  
    52.   
    53.     /* the size is invalid if it is smaller than the number of 
    54.      * elements already inside the hashtable */  
    55.     if (dictIsRehashing(d) || d->ht[0].used > size)  
    56.         return DICT_ERR;  
    57.   
    58.     /* Allocate the new hashtable and initialize all pointers to NULL */  
    59.     n.size = realsize;  
    60.     n.sizemask = realsize-1;  
    61.     n.table = zcalloc(realsize*sizeof(dictEntry*));  
    62.     n.used = 0;  
    63.   
    64.     /* 如果是在dict的第一次申请空间?那么就直接将n赋给d->ht[0],而且不需要rehash */  
    65.     if (d->ht[0].table == NULL) {  
    66.         d->ht[0] = n;  
    67.         return DICT_OK;  
    68.     }  
    69.   
    70.     /* Prepare a second hash table for incremental rehashing */  
    71.     d->ht[1] = n;  
    72.     d->rehashidx = 0;    // rehashidx! = -1; 表示d进入了rehash阶段  
    73.     return DICT_OK;  
    74. }  
    75.   
    76.   
    77. -------------------------Rehash-----------------------------------------  
    78. /*记得前文:serverCron作为一个定时器事件的处理函数,定时的时间为1ms 
    79. 在serverCron会调用incrementallyRehash()函数去不断的完成rehash任务。 
    80. 这里说“不断的"的意思是,rehash的任务不是一次性的函数调用完成的,可能需要 
    81. serverCron调用多次incrementallyRehash()来完成。 
    82. 下文就是incrementallyRehash()函数和子函数的额调用关系,incrementallyRehash() 
    83. 的执行限时为1ms,在这时间内,dictRehash()会以一定量任务(100)为单元进行d->ht的 
    84. 转移。 
    85. */  
    86.   
    87. incrementallyRehash(void)  
    88.     遍历server.db[],对db中的dict进行rehash,每个dict的限定时间为1ms  
    89.     dictRehashMilliseconds(server.db[j].dict,1)  
    90.         while(dictRehash的执行时间<1ms)  
    91.             dictRehash(d,100)//详见下文源码  
    92.                 将dict->ht[1]取出100个元素(dictEntry) Rehash到dict->ht[0]  
    93.       
    94.   
    95. /* Performs N steps of incremental rehashing. Returns 1 if there are still 
    96.  * keys to move from the old to the new hash table, otherwise 0 is returned. 
    97.  * Note that a rehashing step consists in moving a bucket (that may have more 
    98.  * thank one key as we use chaining) from the old to the new hash table. */  
    99.   
    100. /*将依次将d->ht[1].table[]中的元素搬到d->ht[0].table[],修改相关的used。 
    101. d->rehashidx:记录着当前的hashtable中搬了那一条链表的索引下标 
    102. d->ht[0].table[d->rehashidx] => d->ht[0].table[d->rehashidx]              
    103. 完成一个dict的Rehash后,重置d->rehashidx = -1 */  
    104. int dictRehash(dict *d, int n) {  
    105.     if (!dictIsRehashing(d)) return 0;  
    106.   
    107.     while(n--) {  
    108.         dictEntry *de, *nextde;  
    109.   
    110.         /* Check if we already rehashed the whole table... */  
    111.         //d->ht[0].used == 0 : 说明d->ht[0] 已经全部搬到 d->ht[1]  
    112.         if (d->ht[0].used == 0) {  
    113.             zfree(d->ht[0].table);  
    114.             d->ht[0] = d->ht[1];  
    115.             _dictReset(&d->ht[1]);  
    116.             d->rehashidx = -1;   //该dict的Rehash结束 设置为 -1  
    117.             return 0;  
    118.         }  
    119.   
    120.         /* Note that rehashidx can't overflow as we are sure there are more 
    121.          * elements because ht[0].used != 0 */  
    122.         while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;  
    123.         de = d->ht[0].table[d->rehashidx];  
    124.         /* Move all the keys in this bucket from the old to the new hash HT */  
    125.         while(de) {  
    126.             unsigned int h;  
    127.   
    128.             nextde = de->next;  
    129.             /* Get the index in the new hash table */  
    130.             h = dictHashKey(d, de->key) & d->ht[1].sizemask;  
    131.             de->next = d->ht[1].table[h];  
    132.             d->ht[1].table[h] = de;  
    133.             d->ht[0].used--;   
    134.             d->ht[1].used++;   
    135.             de = nextde;  
    136.         }  
    137.         d->ht[0].table[d->rehashidx] = NULL;  
    138.         d->rehashidx++;  
    139.     }  
    140.     return 1;  
    141. }  
    展开全文
  • 类图 类信息 不可以顺序访问 ...public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { private transient Entry<?

    类图

    在这里插入图片描述

    类信息

    • 不可以顺序访问

    • 底层使用数组来实现

      • Entry<?,?> 是一个链表
    • 也具有负载因子和阈值

    • 修改次数

    • 以及一些不序列化的属性

    public class Hashtable<K,V>
        extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable {
        private transient Entry<?,?>[] table;
        private transient int count;
        private int threshold;
        private float loadFactor;
        private transient int modCount = 0;
    }
    

    构造函数

    • 默认的初始化容量是 11 负载因子是 0. 75
    • 在构造函数中就完成了对hashtable的初始化
    • 默认的阈值 是 选取 initialCapacity * loadFactor 和 Integer.MAX_VALUE - 8 + 1的最小值
        public Hashtable() { 
        }
    
        public Hashtable(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    
            if (initialCapacity==0)
                initialCapacity = 1;
            this.loadFactor = loadFactor;
            table = new Entry<?,?>[initialCapacity];
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        }
    

    添加元素

    • value 不能为空
    • 计算出元素在数组中位置的方法
      • int index = (hash & 0x7FFFFFFF) % tab.length;
        public synchronized V put(K key, V value) {
            // Make sure the value is not null
            // value不能为空
            if (value == null) {
                throw new NullPointerException();
            }
    
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            // 计算出 key再说数组中的位置
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            // 得到这个hash位置的第一个元素
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            // 开始遍历这个hash位置的所有元素
            for(; entry != null ; entry = entry.next) {
                // 如果出现 和 key 相等的元素,就直接覆盖掉, 返回.
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    		// 到这里就意味着, 没有出现 key 相等的元素, 那么就直接在这个hash位置上添加即可
            addEntry(hash, key, value, index);
            return null;
        }
    

    addEntry(int hash, K key, V value, int index)

    • count The total number of entries in the hash table.

    • 修改次数更新

    • 先判断是否需要扩容

      • 扩容条件: hash table 中 entries的数量大于等于 阈值
      • 初始化的时候计算阈值 threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    • 非扩容的时候直接在当前hash位置添加即可

        private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            if (count >= threshold) {
                // Rehash the table if the threshold is exceeded
                rehash();
    
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // Creates the new entry.
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }
    

    扩容

    增加容量并对其进行内部重组哈希表,以便容纳和访问其条目更多效率高。当哈希表中的键数超出了该哈希表的容量以及荷载系数。

    • MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    • 扩容一倍
      • 扩容的时候会重新计算 hash
     
        protected void rehash() {
            // 得到旧数组的长度
            int oldCapacity = table.length;
            Entry<?,?>[] oldMap = table;
    
            // overflow-conscious code
            // 新的容量为旧的2 倍+1
            int newCapacity = (oldCapacity << 1) + 1;
            // 判断扩容之后的大小是否已经到了最大值, 如果到了就直接扩容到最大值
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                if (oldCapacity == MAX_ARRAY_SIZE)
                    // Keep running with MAX_ARRAY_SIZE buckets
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            // 新建一个map 使用扩容后的大小
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
            modCount++;
            // 重写计算出阀值大小
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            
            table = newMap;
    
            // 数据迁移的过程
            for (int i = oldCapacity ; i-- > 0 ;) {
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                    Entry<K,V> e = old;
                    old = old.next;
    				// 重新计算  hash 确定元素在数组中的位置
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }
    

    得到元素

    • 计算 key的 hash值
    • 开始遍历这个hash位置的链表
      • key 的hash值相等, key的equlas相等
    • 找到的时候 返回一个空值
        public synchronized V get(Object key) {
            Entry<?,?> tab[] = table;
            // 计算 key的 hash值
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            // 开始遍历这个hash位置的链表
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                // 确定这个元素
                if ((e.hash == hash) && e.key.equals(key)) {
                    return (V)e.value;
                }
            }
            return null;
        }
    

    删除元素

    • 计算出hash值, 得到在数组中的位置
    • 遍历数组
      • 找到相等的key之后
      • 改变前后指针, 删除当前元素
        public synchronized V remove(Object key) {
            Entry<?,?> tab[] = table;
            // 计算出hash 值
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
     
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    modCount++;
                    if (prev != null) {
                        prev.next = e.next;
                    } else {
                        tab[index] = e.next;
                    }
                    count--;
                    V oldValue = e.value;
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }
    

    遍历

    遍历方式也都是使用的 Collections.synchronizedSet之类的集合来确保线程安全.

        public Set<K> keySet() {
            if (keySet == null)
                keySet = Collections.synchronizedSet(new KeySet(), this);
            return keySet;
        }
    
        public Collection<V> values() {
            if (values==null)
                values = Collections.synchronizedCollection(new ValueCollection(),
                                                            this);
            return values;
        }
    
        private class ValueCollection extends AbstractCollection<V> {
            public Iterator<V> iterator() {
                return getIterator(VALUES);
            }
            public int size() {
                return count;
            }
            public boolean contains(Object o) {
                return containsValue(o);
            }
            public void clear() {
                Hashtable.this.clear();
            }
        }
    
       
        public Set<Map.Entry<K,V>> entrySet() {
            if (entrySet==null)
                entrySet = Collections.synchronizedSet(new EntrySet(), this);
            return entrySet;
        }
    

    小总结

    • 方法都被修饰为同步方法
    • 每次扩容 扩容 2 倍
    • 使用数组 + 链表的方式来存储元素
      • 拥有容量和负载
      • 数组中的entriy 大于等于 阈值的时候会扩容
      • 阈值 = 容量 * 负载因子
    • 判断 key相等的方法
      • 计算出 key的hashcode
      • 使用hashcode 和 表的长度相 % 计算出 key的hash值
      • 当hash值相等并且 key的equlas相等的时候 判断key相等
    展开全文
  • hashmap扩容: 默认大小: 16, 增长因子:0.75 扩容点规则(什么时候扩容): 16*0.75=12 存储方式:数组+链表 ...hashtable扩容: 默认大小: 11, 增长因子:0.75 扩容点规则(什么时候扩容): 11*0.75...
  • 1. StringBuffer、StringBuilder 的扩容机制 StringBuffer、StringBuilder,默认初始化是 16 个字符,默认增容为 原长度+2 → 扩容后:2(n+1)* 代码如下: //默认初始化大小 public StringBuilder() { super(16);...
  • 在复习Java基础容器扩容相关时,发现许多博客写的十分混乱,整理一下源码和结论 ArrayList 默认初始10个大小,每次扩容是原容量的1.5倍,具体代码如下 public ArrayList() { this(10); } int newCapacity = ...
  • Map接口实现类——Hashtable HashTable的基本介绍 1)存放的元素键值对即k-V ...rehash() 扩容 1、底层是有一个数组 hashtable entry[] 第一次初始化大小是11 2、临界值是 8 约等于11*0.75 将entry里面的四个键值对
  • 9.为什么hashtable扩容是2倍+1 

    千次阅读 2020-03-14 22:28:13
    9.为什么hashtable扩容是2倍+1 protected void rehash() { int oldCapacity = table.length;//旧容量 Entry<K,V>[] oldMap = table;//旧的桶数组 // overflow-conscious code ...
  • 说明 有一天晚上、女朋友在床头问HashTable的内部结构是什么?扩容又是什么? 我:这都不知道???...我:然后我就和她一顿说、先是这样在是那样给她解释... 扩容机制是什么时候扩容的、扩容多少? key或value是否能.
  • Hashtable 简介和HashMap一样,Hashtable 也是一个散列表,它存储的内容是键值对(key-value)映射。Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。Hashtable 的函数都是同步的,这...
  • a) ArrayList,默认初始10个大小,每次扩容是原容量的一半,具体代码如下public ArrayList() { this(10); } int newCapacity = (oldCapacity * 3)/2 + 1;public static native void arraycopy(Object src, int ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,361
精华内容 13,344
关键字:

hashtable扩容