前段时间学习了哈希表,由于各种原因,直到今天才有时间写博客,现在让我来谈谈我对哈希表的理解。
哈希表是一种数据结构,它可以提供快速的插入和查找操作。不论hash表中有多少数据,插入和删除,都只需要O(1)的时间复杂度。所以如果不需要有序遍历数据,并且可以提前预测数据量的大小,那么使用哈希表往往是方便和快捷的。
使用哈希表时,由于不同的关键字可能得到同一个哈希地址,这种现象称之为冲突。
在诸多大神们的总结下,有以下几种两种常见的方法解决冲突:
1、开放地址法
即发生冲突时,把冲突的数据项放在数组的其他位置
2、链地址法
即在冲突的位置上设置一个链表结构,把冲突的数据项放入其中。但是当数据量非常巨大时,其性能将大大的降低,这就需要给它进行扩容,称之为rehash。
分析完毕,让我们来谈谈代码吧。
(1)插入方法
计算key的hash值,这里调用hashCode()方法来计算hash值;
计算index值,作为table的下标,即table[index]
private int getKey(String id){
int key=id.hashCode();
int index=(key)%(array.legth);
return index;
}
public void add(E e){
int index=getKey(e.getId());
if(array[index]==null){
LinkedList<E> l=new LinkedList<E>();
l.add(e);
array[index]=l;
}else{
array[index].add(e);
}
if((count++)>=threshold){
rehash(2*array.length);
}
}
(2)查找方法
public E get(String id){
int index=getKey(id);
//遍历链表
for(int i=0;i<array[index].size();i++){
if(array[index].element().getId()==id){
E e=array[index].element();
return e;
}
}
return null;
}
(3)删除方法
public void remove(String id){
int index=getKey(id);
for(int i=0;i<array[index].size();i++){
if(array[index].element().getId()==id){
E e=array[index].remove();
}
}
(4)哈希表通用方法演示程序
Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
for(int i=0;i<=10000000;i++){
numbers.put("hash"+i, i);
}
long time1=System.currentTimeMillis();
Integer n = numbers.get("hash1000000");
long time2=System.currentTimeMillis();
long s = time2-time1;
System.out.println("查询时间为:"+s);
Integer nn = numbers.get("hash88");
if(n != null)
System.out.println(n);
System.out.println(nn);
}
<!--EndFragment-->
相关推荐
浅谈哈希表及哈希冲突
下面小编就为大家带来一篇浅谈哈希表存储效率一般不超过50%的原因。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
哈希表是一种高效的数据结构。本文分五个部分:首先提出了哈希表的优点,其次介绍了它的基础操作,接着从简单的例子中作了效率对比,指出其适用范围以及特点,然后通过例子说明了如何在题目中运用哈希表以及需要注意...
+ [哈希表](#哈希表) + [Splay](#splay) * [图论](#图论) + [图论](#图论-1) + [模型建立](#模型建立) + [网络流](#网络流) + [最短路](#最短路) + [欧拉路](#欧拉路) + [差分约束系统](#差分约束系统) + ...
哈希表这个数据结构想必大多数人都不陌生,而且在很多地方都会利用到hash表来提高查找效率。在Java的Object类中有一个方法: public native int hashCode(); 根据这个方法的声明可知,该方法返回一个int类型的...
泛型类最常用于集合,如链接列表、哈希表、堆栈、队列、树等。 像从集合中添加和移除项这样的操作都以大体上相同的方式执行,与所存储数据的类型无关。对大多集合类的操作,推荐使用 .NET Framework 类库中所提供的...
简介 在程序开发过程中,在...“名称/值”对的集合(A Collection of name/value pairs),在不同的语言中,它被理解为对象(Object), 记录(record), 结构(struct), 字典(dictionary), 有趣列表(keyed list), 哈希表(hash
在SQL Server中,我们所常见的表与表之间的Inner Join,Outer Join都会被执行引擎根据所选的列,数据上是否有索引,所选数据的选择性转化为Loop Join,Merge Join,Hash Join这三种物理连接中的一种。理解这三种物理...
6.20 拷贝Python对象.c浅拷贝和深拷贝 6.21 序列类型小结 6.22 练习 第7章 映像和集合类型 7.1 映射类型:字典 7.1.1 如何创建字典和给字典赋值 7.1.2 如何访问字典中的值 ...
6.20 *拷贝python对象、浅拷贝和深拷贝 6.21 序列类型小结 6.22 练习 第7章 映像和集合类型 7.1 映射类型:字典 7.1.1 如何创建字典和给字典赋值 7.1.2 如何访问字典中的值 ...
6.20 *拷贝python对象、浅拷贝和深拷贝 6.21 序列类型小结 6.22 练习 第7章 映像和集合类型 7.1 映射类型:字典 7.1.1 如何创建字典和给字典赋值 7.1.2 如何访问字典中的值 ...
6.20 *拷贝Python对象、浅拷贝和深拷贝 6.21 序列类型小结 6.22 练习 第7章 映像和集合类型 7.1 映射类型:字典 7.1.1 如何创建字典和给字典赋值 7.1.2 如何访问字典中的值 ...