自制哈希表 同 系统Hashtable分析对比

文章目录

定义哈希数组，Node、Entity类put方法get方法remove方法

定义哈希数组，Node、Entity类

//这一部分已在上一篇介绍哈希表的文章中说过 //我的： int length = 100; public Node[] NodeArray = new Node[length]; class Node { //结点类 Entity entity; Node next; } class Entity { //包含结点属性的key、value Object key; Object value; } //Java jdk： final int hash; final K key; V value; Entry<K,V> next; protected Entry(int hash, K key, V value, Entry<K,V> next) { //包含四个值 this.hash = hash; this.key = key; this.value = value; this.next = next; }

put方法

//这一部分已在上一篇介绍哈希表的文章中说过 //我的 //根据键和值往哈希表里加入元素 public void put(Object key, Object value) { if (get(key).equals(key)) { // 必须要用equals，不可以用== System.out.println("已存在！！！"); } else { Node node = new Node(); Entity entity = new Entity(); entity.key = key; entity.value = value; node.entity = entity; int hashCode = key.hashCode(); int index = hashCode % NodeArray.length; if (NodeArray[index] == null) { NodeArray[index] = node; } else { Node root = NodeArray[index]; while (root.next != null) { root = root.next; } root.next = node; } } }

Java jdk中put方法里面又调用了

addEntry：添加元素rehash：扩充Hashtable容量 //Java jdk public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { //jdk中比我多判断了value值是否空 throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; //哈希数组 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; //计算index //按位与得到的是一个二进制数，并且把第一位转化为0 //目的是强制index为正 @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { //每次判断都比我多一个判断哈希值是否相等 V old = entry.value; entry.value = value; return old; //如果该数已经存在就返回原来的值 } } addEntry(hash, key, value, index); return null; //不存在就添加此数然后返回null } private void addEntry(int hash, K key, V value, int index) { modCount++; Entry<?,?> tab[] = table; if (count >= threshold) { //判断如果存入的数溢出，就扩充数组大小 // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; //每增加一个数，计数器就加一 } protected void rehash() { int oldCapacity = table.length; //记录最初表的容量 Entry<?,?>[] oldMap = table; // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) //检测合理性，如果旧容量就等于数组最大容量，就不再分配资源（银行家算法思想） // Keep running with MAX_ARRAY_SIZE buckets return; //否则就扩充到最大值 newCapacity = MAX_ARRAY_SIZE; } Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; //threshold=表容量X装载因子；装载因子=记录数/表容量 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; for (int i = oldCapacity ; i-- > 0 ;) { for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { //把旧表里面的元素全部移位 Entry<K,V> e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; } } }

对比两者put方法：

jdk中的entry直接包含next，后面链表中添加元素，以及rehash中元素移位特别方便，可以直接将entry中所有的内容转移Java jdk最大的特点就是防错： 判断put方法里面传入的value是否为null判断要添加的值是否已经存在，并且同时对比了key和hash的值，key用.equal方法判等addEntry方法里面，判断是否溢出rehash方法检测合理性 Java jdk中设置了扩容的功能，扩容缺点：需要花费很长时间转移哈希表里面的所有元素，所以，在容量满的时候，再去添加一个元素，就要等待很长时间

get方法

我的：首先找到数组中的结点，判断是否相等，不等就往链表里面遍历，中间两次判错

public Object get(Object key) { Object value; int hashCode = key.hashCode(); int index = hashCode % length; if (NodeArray[index] == null) { return "该数不存在"; } else { Node root = NodeArray[index]; while (!root.entity.key.equals(key)) { // 这个地方千万不能用== if (root.next != null) { root = root.next; } else { return "该数不存在"; } } value = root.entity.value; } return value; }

Java jdk

public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; } 因为把节点的属性放在了entry中，下面就特别方便简洁

remove方法

我的，其中有个地方要注意： 不可以用root==null来清空root里面存放的内容，因为root只是定义的一个变量

public void remove(Object key) { if (!get(key).equals(key)) { // 必须要用equals，不可以用== System.out.println("该数不存在！！！"); } else { int hashCode = key.hashCode(); int index = hashCode % length; if (NodeArray[index] == null) { System.out.println("该数不存在"); } else { Node root = NodeArray[index]; Node pre = new Node(); pre.next = root; while (!root.entity.key.equals(key)) { // 这个地方千万不能用== // 如果数组里面index位置的key不等于要找的，就往下找 if (root.next != null) { root = root.next; pre = pre.next; } else { System.out.println("该数不存在"); } } if (root.next == null) { // 如果是尾节点 NodeArray[index] = null; //之前在这里出错了很多次，最后想到直接改数组就好了 } else { // 不是尾节点 pre.next = root.next; } } } }

Java jdk：

public synchronized V remove(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)tab[index]; for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; //这里一样改的数组，而不是结点 } count--; V oldValue = e.value; e.value = null; return oldValue; } } return null; } 上面的remove和get方法思路都差不多put方法有很大不同 下篇“==”和.equals区别HashMap