hashmap,hashtable,hashset

关于Hash表:  也叫散列表, 本质是通过对Key进行计算得到Value存放的地址,以达到快速读取的目的,  快速读取是优点, 遍历和排序是缺点.
初始化Hash表的时候需要一个确定大小的容量,才能实现地址的匹配, 当容量不够时,需要扩大容量(一半是翻倍)并重新计算全部的地址,性能在此时下降很快, 所以哈希表适合预先知道容量,不需要遍历和排序的, 需要快速查找的数据结构

hashtable 和 hashmap 的区别:
1,hashtable 是同步的(同时只能有一个线程可以操作), key和value不能为null
2,hashmap 是异步的, key和value能为null

关键字: hashmap hashtable hashset 
Hashtable类  
  　　Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。  
  　　添加数据使用put(key,   value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。  
  Hashtable通过initial   capacity和load   factor两个参数调整性能。通常缺省的load   factor   0.75较好地实现了时间和空间的均衡。增大load   factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。  
  使用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：  
  　　　　Hashtable   numbers   =   new   Hashtable();  
  　　　　numbers.put(“one”,   new   Integer(1));  
  　　　　numbers.put(“two”,   new   Integer(2));  
  　　　　numbers.put(“three”,   new   Integer(3));  
  　　要取出一个数，比如2，用相应的key：  
  　　　　Integer   n   =   (Integer)numbers.get(“two”);  
  　　　　System.out.println(“two   =   ”   +   n);  
  　　由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。  
  　　如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。  
  　　Hashtable是同步的。  
   
  HashMap类  
  　　HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null   value和null   key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load   factor过低。  
   
  WeakHashMap类  
  　　WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。 



HashSet请参考对Set的描述  
   
          Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。  
  　　Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。　　请注意：必须小心操作可变对象（Mutable   Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。 
两个通用 Set实现是HashSet   和TreeSet。要决定用哪一个，那是非常简单明了的。   HashSet   要快得多   (对大多数操作是常数时间之于对数时间（constant   time   vs.   log   time）),   但不提供排序保证。如果你需要使用   SortedSet   中的操作，或者按顺序迭代对你来说是重要的，那么请使用   TreeSet。   否则，使用   HashSet。   在大多数时间都不使用   HashSet   ，对你来说是个公平的博弈。    
   
  　　关于   HashSet，有一件事应该牢记，即就条目数和容量之和来讲，迭代是线性的。因此，如果迭代性能很重要，那就应该慎重选择一个适当的初始容量。容量选得太大，既浪费空间，也浪费时间。   默认的初试容量是101,   一般来讲，它比你所需要的要多。可以使用   int   构造函数来指定初始容量。要分配   HashSet   的初始容量为17:     
  Set s = new HashSet(17);    
   
  　　HashSets   另有一个称作   装载因数（load   factor）   的"调整参数（tuning   parameter）"   。如果你非常在乎你的   HashSet   的空间的使用，请阅读   HashSet   文本以获取详细信息。否则，就使用默认值吧。如果你接受默认装载因数，但你确实又想指定初始容量，那么，选一个大约是你期望你的   Set   将增长到的容量的两倍的数。如果你的猜测不着边，它也可以增长，或只是浪费一点空间。但都没有大问题。如果你知道有关正确尺寸的一个最佳值，用它吧；如果不知道，那就使用一个旧的值，或使用一个偶数值。它真的不是非常重要。这些事情只能使   HashSet   稍稍变好一点点。    
   
  　　TreeSet   没有调整参数。除   clone   之外，HashSet   和   TreeSet   都仅有那些由它们各自的接口所要求的操作   (Set   和   TreeSet)，而没有任何别的操作。




文章2

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

　　对哈希表的使用者一一人来说，这是一瞬间的事。哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

　　哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

　　而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。

然而如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

 哈希表算法-哈希表的概念及作用

　　一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。

　　理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...

如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？

 

哈希表算法哈希表算法
 

用上述得到的数值作为对应记录在表中的位置，得到下表：

哈希表算法哈希表算法
 

上面这张表即哈希表。

如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：

李秋梅:lqm 12+17+13=42 取表中第42条记录即可。

问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？

这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。

 
 哈希表算法-哈希表的构造方法

１、直接定址法

例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。

           但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数

哈希表算法哈希表算法
 

２、数字分析法

有学生的生日数据如下：

年.月.日

75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...

经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。

３、平方取中法

取关键字平方后的中间几位为哈希地址。

４、折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。

例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：

哈希表算法哈希表算法 

５、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

６、随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

５、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

６、随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

５、除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

H(key)=key MOD p (p<=m)

６、随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即

H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。

 

哈希表算法-处理冲突的方法

哈希表算法

如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：

１、开放定址法

Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)

其中m为表长，di为增量序列

如果di值可能为1,2,3,...m-1，称线性探测再散列。

如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)

称二次探测再散列。

如果di取值可能为伪随机数列。称伪随机探测再散列。

例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下： 

哈希表算法哈希表算法 

２、再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

３、链地址法

将所有关键字为同义词的记录存储在同一线性链表中。

哈希表算法哈希表算法 

４、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。