哈希表---hashtable和数组

    一列键值对数据，存储在一个table中，如何通过数据的关键字快速查找相应值呢？不要告诉我一个个拿出来比较key啊。

    大家都知道，在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

    具体如何做呢？大家是否有注意到前面说的话：“数组可以通过下标直接定位到相应的空间”，对就是这句，哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

    不知道说到这里，一些不了解的朋友是否大概了解了哈希表的原理，其实就是通过空间换取时间的做法。到这里，可能有的朋友就会问，哈希函数对key进行转换，取余的值一定是唯一的吗？这个当然不能保证，主要是由于hashcode会对数组长度进行取余，因此其结果由于数组长度的限制必然会出现重复，所以就会有“冲突”这一问题，至于解决冲突的办法其实有很多种，比如重复散列的方式，大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数，既 (h(k)+i) mod S , i=1,2,3…… ，直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看


有很多人讨论访问数组和Map哪个快

  直接访问数组下标当然最快咯，O(1)的时间。   可以直接定位到下标所对应的数组的值！！但问题是你通常都不知道要访问的元素的下标是多少，1这个时候就要遍历数组来找到这个元素，这个时候map的优势就体现出来了，通常比数组要快！！
  map是用来查找的。

请问hashtable类里面的hash函数是怎么样的？

他是调用每个类自己本身的hashCode的方法来确定的 

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

	// Makes sure the key is not already in the hashtable.
	Entry tab[] = table;
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % 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.hash应该是这个哈希表中元素得到hashcode的静态变量！！
		e.value = value;
		return old;
	    }
	}
modCount++;
	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
	    rehash();

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

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

这是存入时的代码！！根据获取hashcode 对数组的大小取余！~获取下标！

if ((e.hash == hash) && e.key.equals(key)) 
             {
		V old = e.value;//e.hash
		e.value = value;
		return old;
	    }

看这段代码！但出现key相同时会把第二个存储第一个忽略掉

关于hash函数的如何取看链接
http://baike.baidu.com/view/549615.htm
下面看两个面试题

a)请问哈希表 (hashtable) 是如何存储数据的 ？

答案： Hashtable 是用来存储 key 和 value 对的数据结构 , 根据设定的 hash 函数 H(key) 和处理冲突的方法将一组关键字（ key ）映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中存储位置，这种表便成为 hashtable.

b)是否两个键值通过 hash 函数产生的映射地址会一样？怎么办？

答案 : 是，一般情况下，完全避免冲突是很难的。因为通常关键字集合会比目标地址空间大。哈希函数要尽量避免冲突（避免不同的关键字产生相同的 hash 值），使一组关键字的哈西地址尽可能的均匀分布在整个地址区间。所以有一些冲突处理方法：开放定址法，再哈希法，链地址法（用链表保存冲突的值），公共溢出区。