`
jaychang
  • 浏览: 734758 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

SmartHashSet只是为了解释HashSet的原理

阅读更多

写该类的目的只是为了解释下HashSet的大致实现原理,主要要说明的思想是如何解决哈希冲突,在这里使用的是链表来解决哈希冲突。暂时未支持泛型^_^

 

 

一、首先给出实现的原理图

 

      SmartHashSet原理图

 

      一行可以看做一个链表,而第一列的所有Node节点是由Node[] nodes数组构成Node节点用于存放集合的数据,这个图不太科学,其实第一列的结点间不应该有箭头,因为是数组么,而不是链表,说明一下哈,以及寻找下一节点,在这里作为SmartHashSet的内部类使用

      Node定义如下:

 

private static class Node {
		/** 每个集合中元素的值 */
		private Object value;
		/** 链表中当前的节点的下一个节点 */
		private Node next;

		public Node(Object value) {
			this.value = value;
		}

		public Object getValue() {
			return value;
		}

		public void setValue(Object value) {
			this.value = value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}
	}

 

    二、完整的代码

   

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Collection;

/**
 * 无聊时写的,用于解释HashSet的原理,处理哈西冲突的方法为链表来解决 暂时未引入泛型
 * 
 * @author jaychang
 * 
 */
public class SmartHashSet implements Iterator, Iterable {
	/** 当前集合的大小 */
	private int size = 0;
	/** 这个叫法其实不好,这里的capacity还是不要解释为容量,容量可以无限大,这里该解释为数组大小 */
	private int capacity = 16;
	/** 用于迭代该集合时用到 */
	private int currentIndex = 0;
	/** 节点数组 */
	private Node[] nodes;
	/** 迭代时用到的,为该集合中的所有元素 */
	private Object[] objs;

	/** SmartHashSet内部类,用于存放元素值,以及构成实现SmarjtHashSet的数据结构 */
	private static class Node {
		/** 每个集合中元素的值 */
		private Object value;
		/** 链表中当前的节点的下一个节点 */
		private Node next;

		public Node(Object value) {
			this.value = value;
		}

		public Object getValue() {
			return value;
		}

		public void setValue(Object value) {
			this.value = value;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}
	}

	/**
	 * 默认构造,初始容量为16
	 */
	public SmartHashSet() {
		super();
		this.nodes = new Node[capacity];
	}

	/**
	 * 定义初始容量的构造
	 * 
	 * @param initialCapacity
	 */
	public SmartHashSet(int initialCapacity) {
		super();
		this.capacity = initialCapacity;
		this.nodes = new Node[initialCapacity];
	}

	/**
	 * 将集合中的所有元素加入该SmartHashSet对象中
	 * 
	 * @param c
	 *            Collection集合接口
	 * @return 只要有一个元素加入不成功,那么就返回false,只有所有元素都加入成功才返回true;
	 */
	public boolean addAll(Collection c) {
		Object[] values = c.toArray();
		for (int i = 0; i < values.length; i++) {
			if (!add(values[i])) {
				for (int j = 0; j < i; j++) {
					remove(values[j]);
				}
			}
			return false;
		}
		return true;
	}

	/**
	 * 删除所有元素
	 * 
	 * @param c
	 *            Collection集合接口
	 * @return 只要有一个元素加入不成功,就返回false,所有元素都删除成功了,则返回true
	 */
	public boolean removeAll(Collection c) {
		Object[] values = c.toArray();
		for (int i = 0; i < values.length; i++) {
			if (!remove(values[i])) {
				for (int j = 0; j < i; j++) {
					add(values[i]);
				}
				return false;
			}
		}
		return true;
	}

	/**
	 * 向SmartHashSet对象中添加一个元素
	 * 
	 * @param o
	 *            要添加的元素
	 * @return 如果集合中不存在该元素,就添加成功,并返回true,否则返回false
	 */
	public boolean add(Object o) {
		// 得到对象o哈希值所对应的索引值
		int index = o.hashCode() % capacity;
		Node pNode = nodes[index];
		// 该数组的这一索引处无元素,则将o加入到该处
		if (pNode == null) {
			nodes[index] = new Node(o);
			size++;
			return true;
			// 如果该索引处的元素,与o相同,则不能加入
		} else {
			Node nextNode = null;
			while (!pNode.equals(o) && (nextNode = pNode.getNext()) != null) {
				pNode = nextNode;
			}
			// 如果pNode.equals(o)为true,那么nextNode必定为null,即已经到了链表尾
			if (!pNode.getValue().equals(o)) {
				// 将元素加入到链表尾部
				pNode.setNext(new Node(o));
				size++;
				return true;
			}
		}
		return false;
	}

	/**
	 * 从该SmartHashSet中删除一个元素才
	 * 
	 * @param o
	 *            要删除的元素值
	 * @return 如果要删除的元素在该SmartHashSet集合中存在,删除成功,返回true,否则返回false
	 */
	public boolean remove(Object o) {
		for (int i = 0; i < capacity; i++) {
			Node prevNode = nodes[i];
			if (prevNode != null && !prevNode.getValue().equals(o)) {
				Node pNode = null;
				// 寻找pNode节点,该节点的值具有与o相同
				while ((pNode = prevNode.getNext()) != null
						&& !pNode.getValue().equals(o)) {
					prevNode = pNode;
				}
				if (pNode != null) {
					prevNode = pNode.getNext();
					// 删除pNode节点
					pNode = null;
					size--;
					return true;
				}
			} else if (prevNode == null) {
				continue;
			} else {
				nodes[i] = null;
				size--;
				return true;
			}
		}
		return false;
	}

	/**
	 * 判断该SmartHashSet中是否存在指定的元素
	 * 
	 * @param o
	 *            指定的元素
	 * @return 如果指定的元素在该SmartHashSet中存在则返回true,否则返回false
	 */
	public boolean contains(Object o) {
		for (int i = 0; i < capacity; i++) {
			Node pNode = nodes[i];
			while (pNode != null) {
				if (pNode.getValue().equals(o)) {
					return true;
				}
				pNode = pNode.next;
			}
		}
		return false;
	}

	/**
	 * 判断该SmartHashSet中是否无元素
	 * 
	 * @return 如果没有元素则返回true,否则返回false
	 */
	public boolean isEmpty() {
		return size == 0 ? true : false;
	}

	/**
	 * 获取集合的大小,即集合中的元素个数
	 * 
	 * @return 集合中元素个数
	 */
	public int size() {
		return size;
	}

	/**
	 * 将集合中的元素以数据的形式返回
	 * 
	 * @return Object数组
	 */
	public Object[] toArray() {
		Object[] values = new Object[size];
		int count = 0;
		for (int i = 0; i < capacity; i++) {
			if (nodes[i] != null) {
				Node p = nodes[i];
				while (p != null) {
					values[count++] = p.getValue();
					p = p.next;
				}
			}
		}
		return values;
	}

	/**
	 * 判断是否还有元素
	 * 
	 * @return 如果还有元素则返回true,否则返回false
	 */
	public boolean hasNext() {
		return currentIndex < size ? true : false;
	}

	/**
	 * 获取迭代的下一个元素
	 * 
	 * @return 下一个元素
	 */
	public Object next() {
		return this.objs[currentIndex++];
	}

	/**
	 * 将当前迭代到的元素从SmartHashSet对象中删除
	 */
	public void remove() {
		remove(this.objs[currentIndex]);
	}

	/**
	 * 清除所有元素
	 */
	public void clear() {
		this.nodes = null;
		this.nodes = new Node[capacity];
		this.size = 0;
		this.currentIndex = 0;
		this.objs = null;

	}

	/**
	 * 仅保留 set 中那些包含在指定 collection 中的元素(可选操作)。 换句话说,移除此 set 中所有未包含在指定 collection
	 * 中的元素。 如果指定的 collection 也是一个 set,则此操作会实际修改此 set,这样其值是两个 set 的一个交集。
	 * 
	 * @param c
	 *            Collection集合
	 * @return 如果此 set 由于调用而发生更改,则返回 true,否则返回false
	 */
	public boolean retainAll(Collection c) {
		int curSize = size;
		Object[] retainObjs = c.toArray();
		Object[] allObjs = toArray();
		int[] indexNeedNotBeDel = new int[allObjs.length];
		Arrays.fill(indexNeedNotBeDel, -1);
		for (int i = 0; i < retainObjs.length; i++) {
			for (int j = 0; j < allObjs.length; j++) {
				if (retainObjs[i].equals(allObjs[j])) {
					indexNeedNotBeDel[j] = 1;
				}
			}
		}
		for (int k = 0; k < allObjs.length; k++) {
			if (indexNeedNotBeDel[k] == -1) {
				remove(allObjs[k]);
			}
		}
		return curSize > size ? true : false;
	}

	/**
	 * 是否包含所有元素
	 * 
	 * @param c
	 *            Collection集合
	 * @return 只有当所有c集合中的所有元素都在SmartHashSet中存在时,才返回true,否则返回false
	 */
	public boolean containsAll(Collection c) {
		Object[] objs = c.toArray();
		for (int i = 0; i < objs.length; i++) {
			if (!contains(objs[i]))
				return false;
		}
		return true;
	}

	/**
	 * 获得SmartHashSet对象的迭代器
	 * 
	 * @return 迭代器
	 */
	public Iterator iterator() {
		this.objs = toArray();
		this.currentIndex = 0;
		return this;
	}

	public String toString() {

		Object[] allObjs = toArray();
		if (allObjs == null)
			return "[  ]";
		StringBuilder buf = new StringBuilder();
		buf.append("[ ");
		for (int i = 0; i < allObjs.length; i++) {

			buf.append(i == 0 ? " [ " : " , [ ");
			buf.append(allObjs[i].toString());
			buf.append(" ] ");
		}
		buf.append(" ]");
		return buf.toString();
	}
}

   下面详细讲一下,SmartHashSet的工作原理,当一个元素加入到集合中时,先调用该集合的hashCode()方法,根据该hashCode()在经过一定的算法(这里我简单的使用o.hashCode() % capacity来得到该元素应该存放在Node[] nodes数组的索引位置),如果该位置没有元素,即链表的表头为null,那么直接将元素加入。否则就顺序遍历链表,当链表某个结点的值与元素值相同,则本次添加元素操作不成功,如果直到链表末尾都没有与元素值相同的结点,那么将元素加入到此nodes[index]作为表头的链表末尾处。

0
2
分享到:
评论

相关推荐

    HashSet的实现原理

    而HashSet存储的是唯一元素,可以看作是键的集合,只是不存储对应的值。另外,HashMap维护了键的顺序,当使用HashMap时,可以按照插入的顺序来迭代访问键值对,但HashSet是无序的,它不保证元素的迭代顺序,特别是它...

    hashSet底层去重原理.xmind

    hashSet底层去重原理

    HashSet工作原理_动力节点Java学院整理

    对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:

    hashset类的使用

    它基于哈希表的原理来存储不重复的元素,其核心在于利用哈希算法快速定位元素存储位置,从而提高数据存取的效率。本篇将详细介绍Java语言中HashSet类的使用,包括其继承结构、构造函数、常用方法以及实例演示。 ...

    源码解析jdk7.0集合:HashSet的底层实现原理.pdf

    HashSet作为Java集合框架中一个重要的非同步集合实现,它在JDK 7.0中的底层实现原理是基于HashMap来存储和操作数据的。下面就详细介绍HashSet的实现原理。 首先,HashSet是Set接口的一个实现类,它用于存储唯一性的...

    Java面试题之HashSet的实现原理

    Java HashSet的实现原理 HashSet是Java集合框架中的一种set实现,它的实现原理主要基于HashMap。下面我们将详细介绍HashSet的实现原理。 首先,HashSet是Set的一个实现,所以它保证了其中没有重复的元素。在...

    HashSet去重

    为了确保`HashSet`正确地识别重复元素,用户自定义的类必须重写`equals`和`hashCode`方法,以保证逻辑一致性。此外,`HashSet`不仅在去重方面表现出色,还在性能上具有明显优势,特别是在处理大数据量的情况下。

    集合的概念及应用和HashSet保证数据不重复的原理

    关于“HashSet保证数据不重复的原理”,这涉及到HashSet内部的实现。HashSet基于HashMap实现,每个元素都是HashMap的一个键。在添加元素时,HashSet会调用对象的hashCode()方法生成哈希码,然后根据哈希码快速定位...

    HashSet类的用法.pdf

    ### HashSet类的用法 #### 一、概述 `HashSet`是Java集合框架的一部分,它实现了`Set`接口。`HashSet`不允许重复的元素,并且不保证元素的顺序。此外,`HashSet`是非同步的,这意味着多线程环境下的安全问题需要...

    Java面试题 从源码角度分析HashSet实现原理

    HashSet实现原理分析 HashSet是Java集合框架中的一种Set实现,HashSet实现了Set接口,提供了无序、不可重复的集合操作。通过源码分析, HashSet的实现原理可以分为以下几个方面: 1. HashSet的构造函数:HashSet的...

    HashSet详解和使用示例_动力节点Java学院整理

    HashSet是Java编程语言中的一种集合类...然而,在多线程环境下,为了保证线程安全,可以使用`Collections.synchronizedSet`方法来包装HashSet,或者考虑使用ConcurrentHashMap来构建一个线程安全的集合并实现类似功能。

    HashMap与HashTable和HashSet的区别

    ### HashMap与HashTable和HashSet的区别 #### 一、概述 在Java集合框架中,`HashMap`, `HashTable` 和 `HashSet` 是三个重要的数据结构,它们分别实现了`Map`接口和`Set`接口,提供了不同的功能来满足不同的编程...

    java HashSet 集合排序

    java HashSet 集合排序,需要通过利用TreeSet集合排序。2013-10-30。

    集合类HashSet

    在Java编程语言中,集合类是用于存储一组...在黑马程序员_毕向东_Java基础视频教程中,你可能会更详细地学习到关于HashSet的实现原理和实战技巧。通过观看相关视频和实践操作,可以加深对HashSet的理解,提升编程能力。

    c++用vector实现HashSet

    为了用`std::vector`实现HashSet,我们需要关注几个关键点:插入元素、删除元素、检查元素是否存在以及保持元素唯一性。 1. **插入元素**: - 由于`std::vector`不是哈希表,直接插入元素不会保证O(1)的时间复杂度...

    排序之HashSet和TreeSet的区别

    在Java编程语言中,集合框架是处理数据的重要组成部分,其中`...同时,源码阅读也是提升技能的好方法,通过查看`HashSet`和`TreeSet`的源码,可以更深入地了解它们的工作原理,这有助于优化代码并解决可能出现的问题。

    treemap treeset hashset hashmap 简要介绍

    为了正确地工作,`HashSet`要求元素具有良好的`equals()`和`hashCode()`方法实现,以确保元素的唯一性和性能。`HashSet`的底层使用了`HashMap`,实际上,`HashSet`内部就是一个`HashMap`,其中所有值都被设置为`null...

Global site tag (gtag.js) - Google Analytics