如何理解并熟练运用Java底层的数据结构呢，我觉得最好的方法就是自己手撸一遍，所以仿照JavaAPI，手写了简易版的HashSet和HashMap，更加深刻的理解了散列与为什么要散列
（哈希函数采用最简易的除留余数法，冲突的解决采用拉链法）--接口化编程
HashSet
public interface IHashSet<E> {
void add(E e);
/**
* 添加方法
*/
boolean remove(E e);
/**
* 移除方法
*/
boolean isEmpty();
/**
* 判断是否为空
*/
int getSize();
/**
* 返回set集合大小
*/
boolean contains(E e);
/**
* 是否包含元素e
*/
void clear();
/**
* 清空方法
*/
}
public class MyHashSet<E> implements IHashSet<E> {
private int size = 0;
Node[] buckets = new Node[16];//桶数--每个桶都是一个单链表
@Override
public void add(E e) {
int index = hash(e, buckets.length);
Node<E> node = new Node<E>(e);
if(buckets[index] == null) {
buckets[index] = node;
}else {
Node<E> p = buckets[index];
while(p != null) {//添加到链表尾部
E pe = p.elements;
if(pe == e||(pe.equals(e)&&pe.hashCode() == e.hashCode())) {
//set集合去重性
size--;
break;
}
if(p.next == null) {
p.next = node;
break;
}
p = p.next;
}
}
size++;
}
private int hash(E key, int prime) {
return key.hashCode()%prime;
}
@Override
public boolean remove(E e) {//删除结点
int index = hash(e, buckets.length);
if(buckets[index] == null)
return false;
Node<E> p = buckets[index];
Node<E> pre = p;
while(p != null) {
E pe = p.elements;
if(pe == e||pe.hashCode() == e.hashCode()&&pe.equals(e)) {
if(pre == p) {//要删除的是头结点
buckets[index] = p.next;
}else {
pre.next = p.next;
}
size--;
}
if(p.next == null)//gard语句
break;
pre = p;
p = p.next;
}
return false;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean contains(E e) {
int index = hash(e, buckets.length);
if(buckets[index] == null)
return false;
Node<E> p = buckets[index];
while(p != null) {
E pe = p.elements;
if(pe == e||(pe.equals(e)&&pe.hashCode() == e.hashCode()))
return true;
if(p.next == null)
break;
p = p.next;
}
return false;
}
@Override
public void clear() {
for (int i = 0; i < buckets.length; i++) {
buckets[i] = null;
}
size = 0;
}
@Override
public String toString() {
if(size <= 0)
return "[]";
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < buckets.length; i++) {
if(buckets[i] != null) {
Node<E> p = buckets[i];
while(p != null) {
sb.append(p.elements + ",");
if(p.next == null)
break;
p = p.next;
}
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
private static class Node<E>{
E elements;
Node next;
public Node(E elements) {
super();
this.elements = elements;
}
@Override
public String toString() {
return "Node [elements=" + elements + "]";
}
}
}
HashMap
public interface IMap<K, V> {//自定义Map接口
void clear();
/**
* 清除map
*/
boolean contiansKey(K key);
/**
* 检查key是否存在
*/
boolean contiansValue(V value);
/**
* 检查value是否存在
*/
V get(K key);
/**
* 根据key返回value
*/
boolean isEmpty();
/**
* 判断map是否为空
*/
//K[] keySet();
/**
* 返回所有key组成的数组
*/
//V[] valueSet();
/**
* 返回所有value组成的数组
*/
void put(K key, V value);
/**
* 存入一个<K,V>对
*/
V remove(K key);
/**
* 根据key删除一个键值对
*/
int getSize();
/**
* 返回集合大小
*/
//void putAll(IMap<? extends K, ? extends V> map);
/**
* 把另外一个map中的所有键值对存在当前map中
*/
}
public class MyHashMap<K, V> implements IMap<K, V>{
/**
* hash(散列)函数：除留取余法
* 处理冲突方法：拉链法
*/
private Node[] bukets = new Node[16];//桶-(每个桶都用一个单链表表示)
private int size = 0;//Map大小
@Override
public void clear() {
for (int i = 0; i < bukets.length; i++) {
bukets[i] = null;
}
size = 0;
}
@Override
public boolean contiansKey(K key) {
int index = hash(key);
if(bukets[index] == null)
return false;
Node<K, V> p = bukets[index];
while(p != null) {
K pk = p.key;
//Java机制,用户自定义类型可自定义规则改写equals(),hashCode()方法
if(key == pk||(key.equals(pk)&&key.hashCode() == pk.hashCode())) {
return true;
}
if(p.next == null)//gard语句
break;
p = p.next;
}
return false;
}
@Override
public boolean contiansValue(V value) {
for (int i = 0; i < bukets.length; i++) {//遍历所有结点
if(bukets[i] != null) {
Node<K, V> p = bukets[i];
while(p != null) {
if(p.value.equals(value))
return true;
if(p.next == null)
break;
p = p.next;
}
}
}
return false;
}
@Override
public V get(K key) {
int index = hash(key);
if(bukets[index] == null)
return null;
Node<K, V> p = bukets[index];
while(p != null) {
K pk = p.key;
if(pk == key||(pk.hashCode() == key.hashCode()&&pk.equals(key)))
return p.value;
if(p.next == null)//gard语句
break;
p = p.next;
}
return null;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void put(K key, V value) {
Node<K, V> node = new Node<K, V>(key, value);
int index = hash(key);//定桶-散列
if(bukets[index] == null) {//当前位置为空
bukets[index] = node;
size ++;
}else {//拉链法处理冲突
Node<K, V> p = bukets[index];
while(p != null) {//相当于改写do-while
K pk = p.key;
if(key == pk||key.hashCode() == pk.hashCode()&&key.equals(pk)) {
//地址相同或哈希值与内容相同--更新value(原则，不加入重复结点)
p.value = value;
return;
}
if(p.next == null)
break;
p = p.next;
}
p.next = node;//链表尾添加新结点
size++;
}
}
private int hash(K key) {//hash函数--除留取余
return key.hashCode()%bukets.length;
}
@Override
public V remove(K key) {//删除结点操作
int index = hash(key);
if(bukets[index] == null)
return null;
Node<K, V> p = bukets[index];
Node<K, V> pre = p;//复制头结点--每次保持p结点的前一位置
while(p != null) {
K pk = p.key;
if(pk == key||(pk.equals(key)&&pk.hashCode() == key.hashCode())) {
if(p == pre) {//要删除的是头结点
bukets[index] = pre.next;
}else {
pre.next = p.next;
}
size--;
return p.value;
}
if(p.next == null)
break;
pre = p;
p = p.next;
}
return null;
}
@Override
public int getSize() {
return size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < bukets.length; i++) {
if(bukets[i] != null) {
Node<K, V> p = bukets[i];
while(p != null) {
sb.append("(" + p.key + "," + p.value + "),");
p = p.next;
}
}
}
sb.delete(sb.length() - 1, sb.length());
return sb.toString();
}
private static class Node<K, V>{//每个节点都是键值对的集合
K key;
V value;
Node next;
public Node(K key, V value) {
super();
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node [key=" + key + ", value=" + value + "]";
}
}
}
网友评论