hashtable源码

‘壹’ hashmap底层实现原理

hashmap底层实现原理是SortedMap接口能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable

从结构实现来讲，HashMap是：数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。

(1)hashtable源码扩展阅读

从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，除了K，V，还包含hash和next。

HashMap就是使用哈希表来存储的。哈希表为解决冲突，采用链地址法来解决问题，链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

‘贰’ Hashtable，HashMap和TreeMap的区别

Java为数据结构中的映射定义了一个接口java.util.Map，

它有四个实现类，分别是HashMap、HashTable、LinkedHashMap和TreeMap。

这里介绍这4中实例的用法和区别。

关键技术剖析：
Map用于存储键值对，根据键得到值，因此不允许键重复，值可以重复。
l （1）HashMap是一个最常用的Map，它根据键的hashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为null，不允许多条记录的值为null。HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要同步，可以用Collections.synchronizedMap(HashMap map)方法使HashMap具有同步的能力。

l （2）Hashtable与HashMap类似，不同的是：它不允许记录的键或者值为空；它支持线程的同步，即任一时刻只有一个线程能写Hashtable，然而，这也导致了Hashtable在写入时会比较慢。

l （3）LinkedHashMap保存了记录的插入顺序，在用Iteraor遍历LinkedHashMap时，先得到的记录肯定是先插入的。在遍历的时候会比HashMap慢。有HashMap的全部特性。
l （4）TreeMap能够把它保存的记录根据键排序，默认是按升序排序，也可以指定排序的比较器。当用Iteraor遍历TreeMap时，得到的记录是排过序的。TreeMap的键和值都不能为空。

importjava.util.HashMap;
importjava.util.Hashtable;
importjava.util.Iterator;
importjava.util.LinkedHashMap;
importjava.util.Map;
importjava.util.TreeMap;


publicclassTestMap{


publicstaticvoidinit(Mapmap){
if(map!=null){
Stringkey=null;
for(inti=5;i>0;i--){
key=newInteger(i).toString()+".0";
map.put(key,key.toString());
//Map中的键是不重复的，如果插入两个键值一样的记录，
//那么后插入的记录会覆盖先插入的记录
map.put(key,key.toString()+"0");}
}
}

publicstaticvoidoutput(Mapmap){
if(map!=null){
Objectkey=null;
Objectvalue=null;
//使用迭代器遍历Map的键，根据键取值
Iteratorit=map.keySet().iterator();
while(it.hasNext()){
key=it.next();
value=map.get(key);
System.out.println("key:"+key+";value:"+value);
}
//或者使用迭代器遍历Map的记录Map.Entry
Map.Entryentry=null;
it=map.entrySet().iterator();
while(it.hasNext()){
//一个Map.Entry代表一条记录
entry=(Map.Entry)it.next();
//通过entry可以获得记录的键和值
//System.out.println("key:"+entry.getKey()+";value:"+entry.getValue());
}
}
}

(Mapmap,Objectkey){
if(map!=null){
returnmap.containsKey(key);
}
returnfalse;
}

(Mapmap,Objectvalue){
if(map!=null){
returnmap.containsValue(value);
}
returnfalse;
}

publicstaticvoidtestHashMap(){
MapmyMap=newHashMap();
init(myMap);
//HashMap的键可以为null
myMap.put(null,"ddd");
//HashMap的值可以为null
myMap.put("aaa",null);
output(myMap);
}

publicstaticvoidtestHashtable(){
MapmyMap=newHashtable();
init(myMap);
//Hashtable的键不能为null
//myMap.put(null,"ddd");
//Hashtable的值不能为null
//myMap.put("aaa",null);
output(myMap);
}

(){
MapmyMap=newLinkedHashMap();
init(myMap);
//LinkedHashMap的键可以为null
myMap.put(null,"ddd");
myMap.put(null,"aaa");
//LinkedHashMap的值可以为null
myMap.put("aaa",null);
output(myMap);
}

publicstaticvoidtestTreeMap(){
MapmyMap=newTreeMap();
init(myMap);
//TreeMap的键不能为null
//myMap.put(null,"ddd");
//TreeMap的值不能为null
//myMap.put("aaa",null);
output(myMap);
}

publicstaticvoidmain(String[]args){
System.out.println("采用HashMap");
TestMap.testHashMap();
System.out.println("采用Hashtable");
TestMap.testHashtable();
System.out.println("采用LinkedHashMap");
TestMap.testLinkedHashMap();
System.out.println("采用TreeMap");
TestMap.testTreeMap();

MapmyMap=newHashMap();
TestMap.init(myMap);
System.out.println("新初始化一个Map:myMap");
TestMap.output(myMap);
//清空Map
myMap.clear();
System.out.println("将myMapclear后，myMap空了么?"+myMap.isEmpty());
TestMap.output(myMap);
myMap.put("aaa","aaaa");
myMap.put("bbb","bbbb");
//判断Map是否包含某键或者某值
System.out.println("myMap包含键aaa?"+TestMap.containsKey(myMap,"aaa"));
System.out.println("myMap包含值aaaa?"+TestMap.containsValue(myMap,"aaaa"));
//根据键删除Map中的记录
myMap.remove("aaa");
System.out.println("删除键aaa后，myMap包含键aaa?"+TestMap.containsKey(myMap,"aaa"));
//获取Map的记录数
System.out.println("myMap包含的记录数:"+myMap.size());
}
}

输出结果：
采用HashMap
key: null; value: ddd
key: 3.0; value: 3.00
key: aaa; value: null
key: 4.0; value: 4.00
key: 1.0; value: 1.00
key: 5.0; value: 5.00
key: 2.0; value: 2.00
采用Hashtable
key: 4.0; value: 4.00
key: 1.0; value: 1.00
key: 3.0; value: 3.00
key: 5.0; value: 5.00
key: 2.0; value: 2.00
采用LinkedHashMap
key: 5.0; value: 5.00
key: 4.0; value: 4.00
key: 3.0; value: 3.00
key: 2.0; value: 2.00
key: 1.0; value: 1.00
key: null; value: aaa
key: aaa; value: null
采用TreeMap
key: 1.0; value: 1.00
key: 2.0; value: 2.00
key: 3.0; value: 3.00
key: 4.0; value: 4.00
key: 5.0; value: 5.00
新初始化一个Map: myMap
key: 3.0; value: 3.00
key: 4.0; value: 4.00
key: 1.0; value: 1.00
key: 5.0; value: 5.00
key: 2.0; value: 2.00
将myMap clear后，myMap空了么? true
myMap包含键aaa? true
myMap包含值aaaa? true
删除键aaa后，myMap包含键aaa? false
myMap包含的记录数: 1

源码分析：
遍历Map有两种方法：
（1）map的keySet()方法获得键的集合，再调用键集合的iterator方法获得键的迭代器，以此迭代地取出Map中的键，用get方法获得键对应的值，便完成了Map的遍历。代码如下所示：
//使用迭代器遍历Map的键，根据键取值
Iterator it = map.keySet().iterator();
while (it.hasNext()){
key = it.next();
value = map.get(key);
System.out.println("key: " + key + "; value: " + value );
}
（2）使用Map的entrySet方法获得Map中记录的集合，每条对象都是一个Map.Entry对象，使用其getKey方法获得记录的键，使用其getValue方法获得记录的值。代码如下所示：
//或者使用迭代器遍历Map的记录Map.Entry
Map.Entry entry = null;
it = map.entrySet().iterator();
while (it.hasNext()){
//一个Map.Entry代表一条记录
entry = (Map.Entry)it.next();
//通过entry可以获得记录的键和值
//System.out.println("key: " + entry.getKey() + "; value: " + entry.getValue());

‘叁’ v8源码解析之HashTable（v8 0.1.5）

在v8引擎中，哈希表的实现是通过一个名为HashTable的类完成的。它继承自Array类，旨在提供一些通用逻辑以供后续子类使用。我们先来探讨一下其内存布局。

HashTable采用了模板类形式，其成员变量prefix_size和element_size分别代表哈希表中每个元素的大小以及前缀部分的大小。这为实现灵活的存储提供了基础。

接下来，我们对外部定义的内容进行深入分析。首先是Allocate函数，它负责创建一个新的哈希表。该操作是哈希表创建过程中的核心步骤，为后续的插入和查找操作提供了物质基础。

紧接着是FindInsertionEntry函数，该函数通过计算给定键的哈希值来确定插入位置的索引。值得注意的是，哈希表的内存布局中，初始部分用于存储额外的数据，因此真正元素的存储从第n个元素开始。函数返回的索引需要进一步转换为真正的偏移量。

为了适应数据量的增长，EnsureCapacity函数实现了哈希表的扩容操作。这一机制确保了在数据量不断增大的情况下，哈希表能够高效地容纳更多元素，从而维持其性能。

最后是FindEntry函数，它通过键值查找对应位置。找到的位置是相对位置，实际操作时还需要计算出真正的存储位置。这一过程体现了哈希表查找操作的高效性。

综上所述，通过上述功能的协同作用，v8中的HashTable实现了灵活、高效的数据存储与管理，为JavaScript引擎提供了强大且快速的哈希表支持。