T-T..hashtable

刚开始听说hashtable，hash，hashcode，这几个东西放一起真是让人不着头脑，还以为hash是个人名，像Huffman什么的 。原来hash就是散列的意思，hashtable也就是散列表，hash是一种散列算法，而hashcode是根据对象的数据算出来的一个int值。

主要说说hashtable吧，hashtable的实现方式有多重，就常见（我刚搞懂）的拉链法来说，它就是一个链表数组。来看度娘给的图：

具体hashtable里数据怎么存的呢？

先搞定key和value的关联，方法多种， 总之你要存的对象需要被打包成(key+value)的形式(entry<K,V>类的对象)啦，现在可以往hashtable里存了。

hashcode=hashcode(对 象的key)---->hash=hash(hashcode)---->i=indexfor(hash,table.length)，i 就在数组中当下标。当对象的i值重复时（冲突），链表往后接一个，再把数据存进去就行啦。

恩，就是这么个样子，把两种数据结构（数组和链表）组合起来咯~综合了两者的优点，既能够利用数组快速定位，又能使用链表方便的插入和删除，简直鸡汁23333。

呐，既然构思都有了，那如何最大限度的利用hashtable的优点呢~话说如果每个数组中的链表只存一个数据，那hashtable就是个普通数组，同理如果数据都挤着存在一条链表里面，那hashtable就等同于一个链表了，还折腾个毛线。因此就需要把数据尽可能的分散的存到数组的各个位置，数组长度和每个数组元素也就是每条链表的长度要长短合适（合适。。。看到这种词就伐开心了），具体根据需要存数的数量决定咯，因此使用hashtable的前提之一就是对要存储的数据量有一个大致的估计。一个好的hashtable既不浪费空间，又能方便快速的查找到数据，关键就是对分散函数和链表长度的把握啦。

问题又来了。数据是无穷多哒。。一直存一直存，不说爆表至少会使查找速度变慢吧，恩，然后就又出来一个词rehash（感觉英汉词典应该专门给hash有关的词条搞个汇总了），一般Java中都是在容量到达0.72的时候进行rehash。re-，重来，rehash，就是重写个hashtable咯。要求新的hashtable容量更大，原来那个hashtable里的数据也要迁移过来，但是不能直接对应挪窝，否则新的hashtable后半截岂不空了嘛，于是又要搞一个新的hash，把原来hashtable里面的每个数据都取出来，再用新hash计算一遍存到新hashtable里面，保证新hashtable存储的数据是分散的。