Hashtable用一个内部数组用于存放数据：private transient Entry[] table;
Entry是一个内部类：private static class Entry<K,V> implements Map.Entry<K,V>
Entry类似于链表中的节点类，主要属性是hash,key,value,next：
int hash;
K key;
V value;
Entry<K,V> next;
它们的关系为：例如myHashtable.put(myKey,myValue)，则在内部数组中，某下标处，多出一个链表节点myEntry。该节点的数据是：
myEntry.hash = myKey.hashCode();
myEntry.key = myKey;
myEntry.value = myValue;
myEntry.next = previousEntry;//(上一个存放在此的数据)
Hashtable的结构为：
椭圆形是Entry[] table，桶形是Entry。后插入的Entry会被放在查找的前面。
可以看出Entry[] table的每个节点事实上可以存放多条数据，但会降低读取速度。
Hashtable的读取不是像链表一样一个个找的，而是用key通过某函数f(key)直接计算出它在(或可能在)Entry[] table数组中的下标。所以Hashtable的主要算法是一个函数f(key)，该函数的结果是该key在(或可能在)Entry[] table中的下标，然后再在此下标处查找链表中的每一个结点。
显然，Hashtable的主要性能和特性都和f(key)有很大关系，在java的Hashtable中，是这样计算的：
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;//index事实上就是f(key)
用key的hash和0x7FFFFFFF取位与运算，这会将key.hashCode()的高位去除，再取它与table.length的模，得到的结果index必有0<=index<table.length。
其它f(key)的思路有：
1、f(key) = key.hashCode() & (table.length-1)，此时table的长度应为2^n，这样位与运算时，table.length-1的低位都为1，而key.hashCode()的高位都被去除。否则比如若table.length=5(101)，则hash&(length-1)只有两种结果：0(0)和4(100)。所以table中的1,2,3下标处不会有数据，大幅度影响性能。(*一)
2、有的f(key)得到index后，若该位置有值(Entry)，则把index增加一个增量i，直到找到空位置，若到达结尾就从开关再找。这种结构下hash中不存在链表，所以读取速度提高，但写入速度降低，而且可存放的数据小于Entry[]的长度。在这种情况下，table.length最好是一个质数，可以有效提高table中元素的利用率，具体原因就不再赘述了。(*二)
在java中，Hashtable.new有两个重要参数：public Hashtable(int initialCapacity, float loadFactor)
int initialCapacity是初始容量，也就是一开始时Entry[] table的length；
float loadFactor是加载因子，该因子反映了Entry[] table中数据能存放的密度，如：initialCapacity=15,loadFactor=0.5，则该Hashtable最多存放7个数据。注意，在java中，该值是可以大于1的。在上述(*二)中，该值不能大于1。
显然，loadFactor的取值对Hashtable的性能有很大影响，想像一个极端的情况：initialCapacity=1,loadFactor=100，那个该Hashtable能存放100个数据，但它却成为了一个链表，并且比普通链表的效率还低(另外Hashtable的链表是不会有重复值的)。loadFactor的值越小，就越节省内存(Entry[] table中的空元素变少)，但读取速度变慢(Entry[] table中元素的链表变长)。
找到一个合适的loadFactor能提高其总体运行速度，java把这个值设为了0.75：
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
一般loadFactor在1以下，而事实上在很多f(key)的算法中，该值是可以大于1的，如java.util.Hashtable。
了解上述后，Hashtable的get、put、remove操作就变得很简单了：
get：通过f(key)算出index，然后遍历链表。
put：通过f(key)算出index，然后遍历链表，若key已经存在，则改变value，否则插入新的链表节点。其中可能存在rehash操作。
remove：通过f(key)算出index，然后遍历链表，若key已经存在，则进行链表的删除操作。
当Entry[] table中的元素个数超过了initialCapacity*loadFactor，Hashtable就要进行扩容：
protected void rehash()
rehash的过程说起来很简单：提高initialCapacity的值，把原Entry[] table中的值复制到新Entry[] table，复制时因为table.length有变化，所以需要重新计算每个元素的index，即f(key)。复制时需重新计算所有元素(包括链表中的)的新index。
显然rehash是非常耗时的，它也是影响插入数据的速度的很重要的一点。所以如果要进行多次插入操作，可以在Hashtable.new的时候，取一个较大的initialCapacity，这样能显著提高运行速度。在java中，rehash对容量的提升是：
int newCapacity = oldCapacity * 2 + 1;
java的想法似乎是希望所有table.length都是(2^n)-1，而事实上在java的f(key)算法int index = (hash & 0x7FFFFFFF) % tab.length;中，该值对于Entry[] table中元素的链表长度影响并不大，在(*一)中，该值最好是2^n。
为了更好理解和测试Hashtable，我根据java的Hashtable的算法和思想，写了一个ruby版的hashtable。
附上代码：
class Myhashdata
attr_accessor :hash, :key, :value, :nextdata
def initialize hash, key, value, nextdata
@hash = hash
@key = key
@value = value
@nextdata = nextdata
end
end
class Myhash
@@defalutloadfactor = 0.75
def initialize capacity, loadfactor = @@defalutloadfactor
@capacity = capacity
@loadfactor = loadfactor
@threshold = @capacity*@loadfactor
@dataarr = []
@count = 0
end
def msg
puts '@capacity:' + @capacity.to_s
puts '@threshold:' + @threshold.to_s
puts '@count:' + @count.to_s
end
def printall
msg
for i in 0...@capacity
data = @dataarr[i]
puts 'index:'+i.to_s
while !data.nil?
puts "\tkey:" + data.key.to_s
puts "\tvalue:" + data.value.to_s
data = data.nextdata
end
end
end
def gethash obj
return obj.hash
end
def getindex hash
return (hash&2147483647)%@capacity
# return mailto:hash&@capacity
end
def put key, value
hash = gethash(key)
index = getindex(hash)
tmpdata = @dataarr[index]
while !tmpdata.nil?
if tmpdata.key==key && tmpdata.hash==hash
oldvalue = tmpdata.value
tmpdata.value = value
return oldvalue
end
tmpdata = tmpdata.nextdata
end
if @count >= @threshold
# rehash
puts 'count out of threshold, needs rehash'
end
tmpdata = @dataarr[index]
@dataarr[index] = Myhashdata.new(hash, key, value, tmpdata)
@count = @count +1
return nil
end
def get key
hash = gethash(key)
index = getindex(hash)
tmpdata = @dataarr[index]
while !tmpdata.nil?
if tmpdata.key==key && tmpdata.hash==hash
return tmpdata.value
end
tmpdata = tmpdata.nextdata
end
return nil
end
def remove key
hash = gethash(key)
index = getindex(hash)
tmpdata = @dataarr[index]
prev = nil
while !tmpdata.nil?
if tmpdata.key==key && tmpdata.hash==hash
if prev.nil?
@dataarr[index] = tmpdata.nextdata
else
prev.nextdata = tmpdata.nextdata
end
@count = @count - 1
return tmpdata.value
end
prev = tmpdata
tmpdata = tmpdata.nextdata
end
return nil
end
def rehash newcapacity = nil
oldcapacity = @capacity
if !newcapacity.nil? && newcapacity>oldcapacity
@capacity = newcapacity
else
@capacity = oldcapacity*2-1
end
@threshold = @capacity*@loadfactor
newdataarr = []
for i in 0...oldcapacity
tmpdata = @dataarr[i]
while !tmpdata.nil?
olddata = tmpdata.nextdata
index = getindex(tmpdata.hash)
tmpdata.nextdata = newdataarr[index]
newdataarr[index] = tmpdata
tmpdata = olddata
end
end
@dataarr = newdataarr
end
end