class Node{//节点数据结构
private Object value;//节点的值
private Node next;//链表中指向下一结点的引用
/*提供了常见的操作*/
public Node(Object value){this.value = value;};
public Object getValue() {return value;}
public Node getNext() {return next;}
public void setNext(Node next){this.next=next;}
}
public class MyHashSet {//Hash数据结构
private Node[] array;//存储数据链表的数组
private int size = 0;//表示集合中存放的对象的数目
public MyHashSet(int length){
array = new Node[length];//创建数组
}
public int size(){return size;}
private static int hash (Object o){ //根据对象的哈希码得到一个优化的哈希码,
//算法参照java.util.HashMap的hash()方法
int h = o.hashCode();
h += ~(h<<9);
h ^= (h>>>14);
h += (h<<4);
h ^= (h>>>10);
return h;
}
private int indexFor(int hashCode){ //根据Hash码得到其索引位置
//算法参照java.util.HashMap的indexFor()方法
return hashCode & (array.length-1);
}
public void add(Object value) {//把对象加入集合,不允许加入重复的元素
int index = indexFor(hash(value));//先根据value得到index
System.out.println("index:" + index + " value:" + value);
Node newNode = new Node(value);//由value创建一个新节点newNode
Node node = array[index];//由index得到一个节点node
if (node == null) {//若这个由index得到的节点是空,则将新节点放入其中
array[index]=newNode;
size++;
} else {//若不为空则遍历这个点上的链表(下一个节点要等于空或者该节点不等于新节点的值--不允许重复)
Node nextNode;
while (!node.getValue().equals(value) && (nextNode = node.getNext())!=null) {
node = nextNode;
}
if (!node.getValue().equals(value)) {//若值不相等则加入新节点
node.setNext(newNode);
size++;
}
}
}
public boolean contains(Object value){
int index = indexFor(hash(value));
Node node = array[index];
while (node!=null && !node.getValue().equals(value)) {
node = node.getNext();
}//横向查找
if (node!=null && node.getValue().equals(value)) {
return true;
} else {
return false;
}
}
public boolean remove(Object value) {
int index = indexFor(hash(value));
Node node = array[index];
if (node!=null && node.getValue().equals(value)) {//若是第一个节点就是要remove的
array[index]=node.getNext();
size--;
return true;
}
Node lastNode = null;
while (node!=null && !node.getValue().equals(value)) {//若不是第一个节点就横向查找
lastNode = node;//记录上一个节点
node = node.getNext();
}
if (node!=null && node.getValue().equals(value)) {
lastNode.setNext(node.getNext());
size--;
return true;
}else {
return false;
}
}
public Object[] getAll() {
Object [] values = new Object[size];
int index = 0;
for (int i = 0; i < array.length; i++) {
Node node = array[i];
while (node!=null) {
values[index++]=node.getValue();
node = node.getNext();
}
}
return values;
}
public static void main(String[] args) {
MyHashSet set = new MyHashSet(6);
Object [] values = {"Tom","Mike","Mike","Jack","Mary","Linda","Rose","Jone"};
for (int i = 0; i < values.length; i++) {
set.add(values[i]);
}
set.remove("Mary");
System.out.println("size="+set.size());
values = set.getAll();
for (int i = 0; i < values.length; i++) {
System.out.println(values[i]);
}
System.out.println(set.contains("Jack"));
System.out.println(set.contains("Linda"));
System.out.println(set.contains("Jane"));
}
}
附:Java中的Hash结构有HashSet和HashMap,哈希表中的每个位置称为桶(bucket),当发生哈希冲突时就以链表形式存放多个元素。
这两个数据结构中有如下属性:
容量:桶的数量,例子中是6.
初始容量:创建时桶的个数。
大小:元素的数目。
负载因子(Load factor):size/capacity,小的冲突少,这两个类可以指定负载因子。当哈希表的负载达到用户设定的负载因子时会自动成倍增加容量,并且重新分配元素位置。默认为0.75,兼顾时间和空间开销。
分享到:
相关推荐
采用java实现的常用hash算法归总。
工具类
别人写的一个一致性hash的java实现,分享下
PersistentIdealHashTree的Java实现
geohash-java a Java implement of Geohash 提供下列接口: Modifier and Type Method and Description String toGeoHash(double lng, double lat) 根据经纬度计算 geohash String toGeoHash(double lng, double lat...
Java实现的Hash Collision DoS Attack
murmurhash-java 这是Viliam Holub对快速非加密murmurhash2算法的一种实现。 它用Java编写,并以32位和64位版本实现。 如果您想了解最新的杂音世界,请查看Guava的类,该类具有murmur3和32位的实现。建造用maven构建...
实现了链表法(Chaining)和开放地址寻址(Open Addressing)中的Hash表实现,开放地址寻址采用双重散列解决冲突
java实现hash sha1
数据库系统原理实验 数据库管理系统...文件存储表、库,根据sql语句实现建表,建库 可以建立索引(B+树) 可以做笛卡尔积(hash) 自然连接(哈弗曼树)等 有查询树结构 可以完成登录权限管理。 下载后有问题可以联系我。
geohash基本原理是将地球理解为一个二维平面,将平面递归分解成更小的子块,每个子块在一定经纬度范围内拥有相同的编码。GeoHash将二维的经纬度转换成一维的字符串。
java实现的图片防篡改功能,采用图片hash生成唯一标识,再进行比对,判断图片是否被篡改过,可运行源码
此资源主要是实现Java中的SHA1加密方式,将资源下载后直接在程序中复制即可使用。
数据库 我自己在 Java 中实现了 SortMergeJoin 和 HashJoin(来自 SQL 的著名 INNER JOIN)。 在更多信息。
到处运行(Write Once, Run Anywhere)”,这意味着开发者可以使用Java编写应用程序,并在支持Java的任何平台上无需重新编译即可运行,这得益于其独特的跨平台性,通过Java虚拟机(JVM)实现不同操作系统上的兼容。...
Hash算法大全(java实现)参照.pdf
Hash算法大全(java实现)汇编.pdf
ConsistentHash 一致性hash算法的 java 和 C++ 实现