散列表学习

散列表的内部数据结构是数组和链表的结合，好处是增删查改速度快，坏处是如果冲突过多会影响性能。

散列表的工作原理就是按照每一个元素给定的键（key）值和散列函数决定这一个元素存放在数组的位置，下次取值时只需给出所需元素的键（key）值，就可以按照散列函数找到存放位置，将此处的元素返回。

在进行存放元素时因数组大小限制，可能会有键（key）值不同但经过散列函数计算后结果相等的元素，这种情况称之为“冲突”，因为数组长度的限制，所以在使用时“冲突”经常出现，所以为了解决这个问题，有两种方法解决这种“冲突”问题。

链接法

当有多个元素的键（key）值不同，但经过散列函数计算后的值相同时，会将这几个元素放到数组中的同一个位置，产生数据丢失，所以可以将这几个元素组成链表，将表头放入数组中，这样就等于是在数组的每一个位置放入了一个链表，链表中储存的是通过散列函数计算后值相同的元素。

代码示例：

/*** @author mojiayi* @date 2019-01-29 04:52* 散列表链接法实现* 通过输入键值与散列函数计算得到元素存放位置* 线程不安全*/
public class MyHashMap<K,V> {/*** 存放元素的数组*/private Object[] cao;/*** 数组默认长度10*/private int capacity = 100;MyHashMap(){cao = new Object[capacity];}MyHashMap(int capacity){cao = new Object[capacity];this.capacity = capacity;}/*** 通过键（key）值计算存放在数组的位置* @param key* @return*/private int getLocation(K key){return key.hashCode() % capacity;}/*** 插入时如果数组位置为空，在节点头部创建一个空节点作为头节点保存在数组中，* 插入元素放在头节点后* 节点使用内部类 Node 实现* @param key* @param value*/public void put(K key, V value){int i = getLocation(key);if(cao[i]==null){Node node = new Node(key, value, null, null);cao[i] = new Node(null, null, node, null);node.pre = (Node) cao[i];return;}Node node = findNode((Node) cao[i], key);if(node != null){node.obj = value;return;}Node tmp = (Node) cao[i];node = new Node(key, value, tmp.next, tmp);tmp.next.pre = node;tmp.next = node;}/*** 根据键（key）值得到数组位置后，* 从头节点开始遍历寻找和传入键（key）值相同的元素* @param node* @param key* @return*/private Node findNode(Node node, K key) {if(key.equals(node.key))return node;if(node.next==null)return null;return findNode(node.next, key);}/*** 根据键（key）值查找元素得到节点的元素值* 返回 Node 对象的 obj 值* @param key* @return*/public V get(K key) {Node node = (Node) cao[getLocation(key)];if(node==null)return null;Node res = findNode(node, key);return res==null?null:res.obj;}public boolean remove(K key){int i = getLocation(key);if(cao[i] == null)return false;Node node = findNode((Node) cao[i], key);if(node == null)return false;if(node.next == null){node.pre.next = null;node.pre = null;node.obj = null;node.key = null;node = null;return true;}System.out.println(node);node.pre.next = node.next;node.next.pre = node.pre;node.pre = null;node.next = null;node.key = null;node.obj = null;node = null;return true;}/*** 内部类* 用来实现链表节点*/private class Node{private K key;private V obj;private Node next;private Node pre;Node(K key, V obj, Node next, Node pre){this.key = key;this.next = next;this.obj = obj;this.pre = pre;}@Overridepublic String toString() {return "["+key+","+obj+"]";}}@Overridepublic String toString() {return "["+key+","+obj+"]";}}@Overridepublic String toString() {StringBuilder builder = new StringBuilder();for(int i = 0; i < cao.length; i++){if(cao[i] != null){Node node = (Node) cao[i];builder.append(node.toString());while(node.next != null){builder.append(node.next.toString());//System.out.println(node);node = node.next;}builder.append("\n");}}return builder.toString();}
}
复制代码