- 浏览: 1235164 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (242)
- java (58)
- netty (14)
- javascript (21)
- commons (13)
- 读书笔记 (5)
- java测试 (6)
- database (5)
- struts2 (8)
- hibernate (6)
- english (27)
- spring (10)
- 生活 (4)
- 多线程 (4)
- 正则表达式 (1)
- 杂项 (1)
- maven (4)
- 数据库 (10)
- 学习笔记 (1)
- mongodb (1)
- 百度bcs (4)
- 云推送javasdk (2)
- webservice (3)
- IllegalAnnotationException: Two classes have the same XML type name (0)
- drools (3)
- freemarker (3)
- tomcat (1)
- html5 (2)
- mq (11)
- fastjson (3)
- 小算法 (2)
最新评论
-
longxitian:
https://www.cnblogs.com/jeffen/ ...
万恶的Mybatis的EnumTypeHandler -
asialee:
ddnzero 写道博主请问FileUtils这个类是哪个包的 ...
使用mockftpserver进行ftp测试 -
ddnzero:
博主请问FileUtils这个类是哪个包的?还是自己的呢?能放 ...
使用mockftpserver进行ftp测试 -
yizishou:
为什么会intMap.get("bbb") ...
浅谈System.identityHashCode -
liguanqun811:
感觉LogManager打开了所有的LogSegment(文件 ...
jafka学习之LogManager
自己实现的HashTable,主要是学习一下Hash的冲突检测以及冲突解决方式,没有详细的测试,希望大家多多指教。
import java.util.Locale; /** * Implement a hash table to store strings (i.e. objects of the Java String * class) * * @author LiYazhou * @version 1.0 */ public class HashTable { /** * The initialize size of this hash table. */ private final static int INITIAL_SIZE = 50; /** * The internal array to hold the elements */ private String[] elements; /** * The real number of this hast table */ private int capacity; /** * The no argument constructor to initialize the HashTable to size 101 */ public HashTable() { this(INITIAL_SIZE); } /** * Creates a hash table to store n items, the size of the underlying array * should be a prime number, roughly 2 * n * * @param n */ public HashTable(int n) { int size = 2 * n; elements = new String[getNearestPrime(size)]; } /** * Inserts the parameter into the hash table, return true if the parameter * was inserted * * @param value * The value to be inserted. * @return Whether or not the value to be inserted. */ public boolean insert(String value) { if (loadFactor() >= 0.75) { reHash(); } return insert(elements, value); } /** * Inserts the parameter into the hash table, return true if the parameter * was inserted * * @param strArray * To insert the value to the strArray array * @param value * The value to be inserted. * @return Whether or not the value to be inserted. */ private boolean insert(String[] strArray, String value) { int hash_key = hash(value, strArray.length); int increment = 1; int probe_counter = 0; int hash_mid = (strArray.length + 1) / 2; while (true) { // Check for overflow if (probe_counter > hash_mid) { return false; } String tmp = strArray[hash_key]; // Empty slot if (tmp == null) { break; // Position already taken, duplicate keys are not allowed } else if (tmp.equals(value)) { return false; // Handles collision using h+i^2 } else { hash_key = (hash_key + increment) % strArray.length; increment += 2; probe_counter++; } } strArray[hash_key] = value; capacity++; return true; } /** * return true if the given string is in the table, false otherwise * * @param str * The value to be checked in this hash table * @return Whether or not the value is in this hash table. */ public boolean lookUp(String str) { int hash_key = hash(str, elements.length); int increment = 1; int probe_counter = 0; int hash_mid = (elements.length + 1) / 2; while (true) { // Overflow encountered if the probe is bigger than hash_size/2 if (probe_counter > hash_mid) { return false; } String tmp = elements[hash_key]; // Record empty for the key if (tmp == null) { break; } else if (tmp.equals(str)) { return true; } else { hash_key = (hash_key + increment) % elements.length; increment += 2; probe_counter++; } } return false; } /** * Returns the size of the hash table (the size of the underlying array) * * @return The size of the hash table */ public int length() { return elements.length; } /** * Returns the number of strings currently stored in the hash table * * @return The number of strings currently stored in the hash table */ public int getNum() { return capacity; } /** * The current load factor of this hash table. * * @return The current load factor of this hash table. */ private float loadFactor() { return (float) capacity / elements.length; } /** * This method is to get the next nearest prime number after size * * @param size * The base which you want to find * @return The next nearest prime number after size */ private int getNearestPrime(int size) { boolean isPrime = checkPrime(size); while (!isPrime) { size++; isPrime = checkPrime(size); } return size; } /** * This is the hash function to return a hash code according to the key * * @param word * The key which you want to generate the hash code * @param size * The size of current array's size * @return The hash code for the give word */ private int hash(String word, int size) { word = word.toLowerCase(Locale.ENGLISH); int hashValue = 0; for (int i = 0; i < word.length(); i++) { hashValue = ((hashValue * 32) + (word.charAt(i) - 'a')) % size; } if(hashValue < 0){ hashValue = hashValue + size; } return hashValue; } /** * This method is to implement the rehash function when the load factor is * greater than the initial load factor. */ private void reHash() { capacity = 0; String[] newArray = new String[getNearestPrime(2 * elements.length)]; for (int i = 0; i < elements.length; i++) { if (elements[i] != null) { insert(newArray, elements[i]); } } elements = newArray; } /** * This method is to check whether this number is a prime value or not * * @param n * The value which you want to check whether it is a prime value * @return Whether the given value is a prime value. */ private boolean checkPrime(int n) { if (n < 1) { return false; } if (n % 2 == 0) { return false; } for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) { return false; } } return true; } }
评论
10 楼
yegaofei
2010-04-01
借楼主的帖子问个问题:
当我们遍历Hashtable的key集合时,常用Enumeration的nextElement()方法,我看了下jdk的代码,nextElement()方法是以从后往前的顺序遍历的,而且注释写的是为了更快速的遍历。
我想问一下,为什么从后往前的速度会比较快?
当我们遍历Hashtable的key集合时,常用Enumeration的nextElement()方法,我看了下jdk的代码,nextElement()方法是以从后往前的顺序遍历的,而且注释写的是为了更快速的遍历。
我想问一下,为什么从后往前的速度会比较快?
9 楼
asialee
2010-03-07
captmjc 写道
另外,对于checkPrime,建议lz google "prime sieve",并以此为基础,实现准备好前N个Prime (http://primes.utm.edu/lists/small/1000.txt,10000.txt ...)以加快速度
非常感谢
8 楼
captmjc
2010-03-07
asialee 写道
robertliudeqiang 写道
楼上说的对,你这个实现的类似HashSet。在JDK里,HashSet是基于HashMap实现的。
对程序的个人观点:
1 你使用的是“开放寻址法”,个人觉得没有JDK里面HashMap用的bucket的结构有效率,主要原因是当loadFactor比较高的时候冲突会比较多。
2 private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数,特别是当n很大的时候,只需要找一个可能的大素数就行了,应该有相应算法。
对程序的个人观点:
1 你使用的是“开放寻址法”,个人觉得没有JDK里面HashMap用的bucket的结构有效率,主要原因是当loadFactor比较高的时候冲突会比较多。
2 private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数,特别是当n很大的时候,只需要找一个可能的大素数就行了,应该有相应算法。
非常感谢,看来我真的有修改了,应该叫做HashSet,还有,我没有去看JDK里面的HashSet的实现,对它检测冲突的方法也不是很了解,建议给我扫盲一下。
HashSet其实利用了HashMap
7 楼
captmjc
2010-03-07
另外,对于checkPrime,建议lz google "prime sieve",并以此为基础,实现准备好前N个Prime (http://primes.utm.edu/lists/small/1000.txt,10000.txt ...)以加快速度
6 楼
asialee
2010-03-06
robertliudeqiang 写道
楼上说的对,你这个实现的类似HashSet。在JDK里,HashSet是基于HashMap实现的。
对程序的个人观点:
1 你使用的是“开放寻址法”,个人觉得没有JDK里面HashMap用的bucket的结构有效率,主要原因是当loadFactor比较高的时候冲突会比较多。
2 private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数,特别是当n很大的时候,只需要找一个可能的大素数就行了,应该有相应算法。
对程序的个人观点:
1 你使用的是“开放寻址法”,个人觉得没有JDK里面HashMap用的bucket的结构有效率,主要原因是当loadFactor比较高的时候冲突会比较多。
2 private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数,特别是当n很大的时候,只需要找一个可能的大素数就行了,应该有相应算法。
非常感谢,看来我真的有修改了,应该叫做HashSet,还有,我没有去看JDK里面的HashSet的实现,对它检测冲突的方法也不是很了解,建议给我扫盲一下。
5 楼
robertliudeqiang
2010-03-06
楼上说的对,你这个实现的类似HashSet。在JDK里,HashSet是基于HashMap实现的。
对程序的个人观点:
1 你使用的是“开放寻址法”,个人觉得没有JDK里面HashMap用的bucket的结构有效率,主要原因是当loadFactor比较高的时候冲突会比较多。
2 private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数,特别是当n很大的时候,只需要找一个可能的大素数就行了,应该有相应算法。
对程序的个人观点:
1 你使用的是“开放寻址法”,个人觉得没有JDK里面HashMap用的bucket的结构有效率,主要原因是当loadFactor比较高的时候冲突会比较多。
2 private boolean checkPrime(int n)
可能有时候并不需要真的找一个素数,特别是当n很大的时候,只需要找一个可能的大素数就行了,应该有相应算法。
4 楼
captmjc
2010-03-06
1, 你说你这个只支出String的,Object[]或者泛型不就可以了
2, 这个貌似实现的是HashSet的类似功能,而不是HashTable的键值对
2, 这个貌似实现的是HashSet的类似功能,而不是HashTable的键值对
3 楼
asialee
2010-03-06
另外,现在这个只是支持String,我主要是想看看冲突检测和解决的。
2 楼
asialee
2010-03-06
robertliudeqiang 写道
asialee 写道
[size=medium]
/**
* Inserts the parameter into the hash table, return true if the parameter
* was inserted
*
* @param value
* The value to be inserted.
* @return Whether or not the value to be inserted.
*/
public boolean insert(String value) {
if (loadFactor() >= 0.75) {
reHash();
}
return insert(elements, value);
}
/**
* Inserts the parameter into the hash table, return true if the parameter
* was inserted
*
* @param value
* The value to be inserted.
* @return Whether or not the value to be inserted.
*/
public boolean insert(String value) {
if (loadFactor() >= 0.75) {
reHash();
}
return insert(elements, value);
}
如果是实现HashTable, ms方法应该是:
public boolean insert(String key, String value);
这个是这样的,JDK的HashTable是用的key的hash值查找的,它里面存储的是Entry,我是直接根据要插入的值生成Hash值的, 实际上查找的时候是直接查找值的。
1 楼
robertliudeqiang
2010-03-06
asialee 写道
[size=medium]
/**
* Inserts the parameter into the hash table, return true if the parameter
* was inserted
*
* @param value
* The value to be inserted.
* @return Whether or not the value to be inserted.
*/
public boolean insert(String value) {
if (loadFactor() >= 0.75) {
reHash();
}
return insert(elements, value);
}
/**
* Inserts the parameter into the hash table, return true if the parameter
* was inserted
*
* @param value
* The value to be inserted.
* @return Whether or not the value to be inserted.
*/
public boolean insert(String value) {
if (loadFactor() >= 0.75) {
reHash();
}
return insert(elements, value);
}
如果是实现HashTable, ms方法应该是:
public boolean insert(String key, String value);
发表评论
-
maven的system scope的依赖在打包的时候不出现在lib里面的解决
2017-09-20 11:21 0上周遇到一个问题,一个sytem scope的依赖,在导出的 ... -
JAVA静态代码块
2015-04-07 16:26 2032今天遇到下面的代码 ... -
StringUtils.repeat函数赏析与疑问
2014-09-01 18:43 6090今天实现一个字符串拼接的一个需求,比如: ... -
java服务的培训ppt
2014-08-30 23:01 1581给应届生培训java web 服 ... -
给新人制定的java学习计划
2014-08-30 22:52 2493花了一点时间,给团队应届生和实习生制定 ... -
获取手机的mac地址
2014-04-10 22:20 3402与IP不同,MAC是指连接WIFI使用的无线网卡的物理地址, ... -
解决errorpage里面取不到Authentication的问题
2013-01-20 23:56 2449本人原创,发现一些网站无道德的抓取 ... -
SimpleDateFormat使用的时候的注意点
2012-12-06 20:59 2054今天在帮助同事查找一个项目bug的时候发现一个很奇怪 ... -
java和javascript的正则表达式有点不同
2012-11-06 18:54 1445今天在项目中遇 ... -
velocity 1.6.4的一个bug
2012-09-10 17:24 2173$.ajax()在Velocity中会冲突, 总之 ... -
一种多数据源分页算法
2012-09-10 17:13 7547以前开发一个系统,需要去多个系统去取数据,简单期间,比 ... -
使用stringBuffer和StringBuilder拼串要注意的问题
2012-07-30 17:30 8094今天在和同事排除一个问题的时候发现,从 ... -
java获取当月的工作日
2012-05-10 12:07 6129在这个记录一下,记录java获取某个月的工作日的代码,方便以 ... -
webservice引用传参
2012-04-19 19:38 1446http://www.blogjava.net/xylz/ar ... -
java获取当天的开始时间,当前周的开始时间
2012-04-16 17:31 19594在程序里面要获取当前的开始时间和结束时间,以及当前天 ... -
edtFTPj源码学习
2012-04-11 16:25 1249下面是edtFTPj的源码学习,下面的类图都是我自己亲手花的, ... -
ftp协议研究
2012-03-12 17:34 1270ACTIVE FTP OPERATION 1、客户端使用源 ... -
西安交通大学的错误日志
2011-12-14 13:30 1010西安交大的网站报错了,记录下出错日志,改天研究一下。 HT ... -
tomcat的favicon.ico的用法
2011-12-01 20:00 22251. web.xml文件添加下面的mime-mapping ... -
htmlunit模拟sso登陆
2011-07-27 14:45 6938import java.io.IOException; ...
相关推荐
在Java中,除了`HashTable`,还有其他实现,如`HashMap`,它在单线程环境下提供了更好的性能,而`ConcurrentHashMap`则在多线程环境下提供高性能且线程安全的解决方案。学习和掌握这些不同的实现方式可以帮助开发者...
在本篇文章中,我们将深入探讨哈希表的实现,特别是基于C语言的简单实现,参考文件"hashtable.c"和"hashtable.h"。 1. 哈希函数:哈希表的核心是哈希函数,它将输入(键或关键字)转换为数组索引。一个好的哈希函数...
c语言实现hashtable,一个key可以对应多个data,c语言实现
HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的。 一,访问接口 创建一个hashtable. hashtable hashtable_new(int size) /其中size表示包含的接点个数。...
《深入解析HashTable:C语言实现的精髓》 在计算机科学中,哈希表(HashTable)是一种数据结构,它实现了关联数组的抽象数据类型,能够快速地进行查找、插入和删除操作。哈希表通过将键(Key)映射到表中的一个位置...
### 基于Hashtable与Session实现的购物车系统 #### 一、引言 随着互联网技术的发展,电子商务网站成为人们日常购物的重要渠道之一。在众多电商功能中,“购物车”作为一个核心组件,允许用户暂时存储选购的商品,在...
本教程将详细讲解如何使用Java中的Session和Hashtable来实现这一功能。 首先,Session是Web应用程序中用于跟踪用户状态的一种机制。在HTTP协议无状态的特性下,Session为我们提供了在多个请求之间保持用户信息的...
var hashtable = (Hashtable)serializer.Deserialize(jsonString, typeof(Hashtable)); ``` 2. **Newtonsoft.Json**:这是更流行和功能强大的第三方库,也被称为Json.NET。它的`JsonConvert.DeserializeObject`方法...
哈希表(Hashtable)是.NET框架中的一种常用数据结构,主要用作键值对存储,它提供了快速的数据存取方式。在WinForm应用程序中,我们可能会利用Hashtable来管理各种对象,尤其是在需要高效查找和操作数据时。下面将...
`HashTable`通过同步每个方法的执行来实现这一点,即在执行`HashTable`的任何方法时,都会锁定整个对象,确保同一时间只有一个线程能够访问或修改`HashTable`。 - **HashMap**: 相较之下,`HashMap`不是一个线程...
`HashMap` 和 `HashTable` 都是 Java 集合框架中非常重要的数据结构,它们都实现了 `Map` 接口,用于存储键值对。尽管它们在功能上有很多相似之处,但在实现细节和性能特性上存在显著差异。 #### 二、主要区别 1. ...
HashMap和HashTable是Java中两个常用的数据结构,都是基于哈希表实现的,但它们之间存在着一些关键的区别。本文将深入探讨HashMap和HashTable的底层原理,并总结常见的面试题。 HashMap的底层原理 HashMap是Java中...
哈希表(HashTable)是一种常见的数据结构,它通过哈希函数将键(Key)映射到数组的索引位置,从而实现快速查找、插入和删除操作。在C语言中实现哈希表,需要理解哈希函数的设计、冲突解决策略以及数据结构的组织...
在ASP.NET中,Hashtable是一种常用的数据结构,它是一个键值对集合,允许程序员存储和检索对象。本篇文章将深入探讨如何在ASP...在WebSite3项目中,可能涉及的就是如何在实际应用中使用这些技巧,实现高效的数据管理。
此外,`Hashtable`实现了`Map`接口,所以也可以使用`entrySet()`方法获取所有键值对的`Set`视图,方便进行遍历和操作。 在实际开发中,由于`Hashtable`的线程安全特性,它通常在需要跨线程共享数据时使用。但是,`...
在Java编程语言中,`HashMap`和`HashTable`是两种非常重要的数据结构,它们都实现了`Map`接口,并提供了键值对的存储方式。这两种数据结构虽然相似,但在实现细节和使用场景上存在显著差异。下面将详细介绍`HashMap`...
- **Hashtable**:该类继承自`Dictionary`类,并且实现了`Map`接口。它最早出现在Java 1.0版本中,可以视为早期实现键值对存储的一种方式。 - **HashMap**:相比之下,`HashMap`是在Java 1.2版本中引入的新类,它...
实现hashtable按值排序和按key排序,可直接运行
在Java编程语言中,`Hashtable`和`HashMap`是两种非常重要的数据结构,它们都实现了`Map`接口,用于存储键值对。尽管它们有着相似的功能,但在实现细节和应用场景上存在显著差异。接下来,我们将详细探讨`Hashtable`...