使用JAVA实现散列的数据结构

发表于   |   分类于 左手代码 计算机基础   |   阅读(131)   |   评论(91)

一、散列

散列是为了解决快速插入和快速查找的功能，它是基于数组+链表来实现的

1.散列结构

散列结构

  • 散列的节点：实际存储的节点
  • 散列函数：hash函数，它通过一定的算法将所存储节点的key转化为一个整数，我们可以根据这个计算出来的整数值来确定它应该存储到散列表的什么位置
  • 散列表：用于存放一系列散列节点的表

注：我们通过key计算出其hashCode值，但不同的key可能其hashCode值相同，这就是所谓的hash碰撞,处理hash碰撞就很多方式，比如重新hash，还有开放地址法等，我们这里采用链表的方式来处理哈希碰撞

2.利用链表来解决hash冲突
  • 如果计算出的hash值，与原来的某个节点相同，而它应该存储的位置被另外一个节点占用了，此时，我们可以在存储位置的节点加上一个next指针，指向新的加入到这个位置的节点

二、动手实现一个散列结构

1.散列表的几个组成部分
  • size : 散列表元素个数　
  • nodes : 存储节点的数组
  • capacity:占用的空间
  • Node : 节点定义
  1.     /**
  2.      * 散列表的大小
  3.      */
  4.     private int size;
  6.     /**
  7.      * 散列表存储节点的数组
  8.      */
  9.     private Node<K, V>[] nodes;
  11.     /**
  12.      * 容量
  13.      */
  14.     private int capacity;
  16.     /*
  17.     * 散列表的节点
  18.     */
  19.     private class Node<K, V> {
  20.     　　//键
  21.         private K key;
  22.         //值
  23.         private V value;
  24.         //键对应的hash码
  25.         private int hashCode;
  26.         //键的下一个节点指针
  27.         private Node<K, V> next;
  28.     }
2.添加元素(包括重置元素值)
  • 新增的元素：该键不存在，查找到元素应该存储的位置，如果所有位置已经被占用，则在应该存储的位置的第后一个节点，通过next指针指向新增的节点
  • 修改元素的值：该键已经存在，查找到元素修改值即可
  1.     /**
  2.      * 添加元素
  3.      * @param key
  4.      * @param value
  5.      * @return
  6.      */
  7.     public boolean put(K key, V value) {
  8.         //1.新添加一个节点
  9.         Node<K, V> node = new Node<K, V>(key, value, null);
  10.         //2.计算出节点存储到数组中的位置
  11.         int index = getIndex(node.getHashCode());
  12.         //3.查找存储的位置上的节点
  13.         Node<K, V> indexNode = (Node<K, V>) nodes[index];
  14.         //4.定义一个是否为新节点的标识(默认为新增节点)
  15.         boolean newNode = true;
  16.         //5.如果插入的位置上节点不存在，那么直接将新增节点放入这个位置即可
  17.         if (indexNode == null) {
  18.             nodes[index] = node;
  19.         } else {
  20.         　　 //否则说明该位置上有其他节点，定义一个当前指针　
  21.             Node<K, V> current = indexNode;
  22.             //6.如果当前节点的下一个节点不为null，即这个位置有不少于2个节点的数据，一直遍历
  23.             while (current.getNext() != null) {
  24.             　　 //7.如果插入的键已经存在　
  25.                 if (key.equals(current.getKey())) {
  26.                     //插入的值存在的话，那么修改它的值，并且将newNode设置为false,即不是新增节点
  27.                     current.setValue(value);
  28.                     newNode = false;
  29.                     break;
  30.                 }
  31.                 current = current.getNext();
  32.             }
  33.             //8.如果是新增节点，设置最后一个节点的next为新增的节点
  34.             if (newNode) {
  35.                 current.setNext(node);
  36.             }
  37.         }
  38.         //9.如果是新增节点，则更新表节点的长度
  39.         if (newNode) {
  40.             this.size ++;
  41.         }
  42.         return true;
  43.     }
3.获取元素
  • 先通过key计算出节点在数组中的存储位置
  • 再在相应的位置上查找与key相等的节点即可
  1.     /**
  2.      * 获取元素值
  3.      * @param k
  4.      * @return
  5.      */
  6.     public V get(K k) {
  7.         //1.获取键对应的索引位置
  8.         int index = getIndex(k.hashCode());
  9.         //2.获取该位置的节点
  10.         Node<K, V> node = nodes[index];
  11.         if (node != null) {
  12.             Node<K, V> current = node;
  13.             //遍历包含节点在内的链表，一直查找到与key相等的节点
  14.             while (current != null) {
  15.                 if (k.equals(current.getKey())) {
  16.                     return current.getValue();
  17.                 }
  18.                 current = current.getNext();
  19.             }
  20.         }
  21.         return null;
  22.     }
4.删除元素值
  • 先通过key找到存储节点的位置
  • 依次遍历位置上所有的节点，并记录遍历的节点的前一个节点，如果当前节点的key与删除的key相等
    • 那么首先获取删除元素的值
    • 如果删除元素的前一个元素为null，即删除的存储位置的第一个元素，那么让存储位置的元素指向当前删除元素的下一个元素
    • 如果删除元素不是第一个元素，那么将删除元素的上一个元素的next指针指向删除元素的下一个元素
    • 删除当前元素存储的值
  1.     /**
  2.      * 删除某个key对应的元素
  3.      * @param key
  4.      * @return
  5.      */
  6.     public V remove(K key) {
  7.         //1.通过key获取在数组中的存储位置
  8.         int index = getIndex(key.hashCode());
  9.         //2.通过位置获取节点
  10.         Node<K, V> current = nodes[index];
  11.         //3.如果不存在，直接返回
  12.         if (current == null) {
  13.             return null;
  14.         }
  15.         //4.定义删除节点的前一个节点
  16.         Node<K, V> prev = null;
  17.         while (current != null) {
  18.             //5.如果查找到key对应的节点
  19.             if (current.getKey().equals(key)) {
  20.                 //获取原值
  21.                 V oldValue = current.getValue();
  22.                 //如果上一个节点不为null，即删除的节点不是所在位置的第一个元素
  23.                 if (prev != null) {
  24.                     //设置前一个节点的next指向删除元素的下一个元素
  25.                     prev.setNext(current.getNext());
  26.                 } else {
  27.                     //将数组对应的位置设置为当前元素的上一个元素(因为第一个元素已经被删除了，所以要更新数组中的对应的元素)
  28.                     nodes[index] = current.getNext();
  29.                 }
  30.                 //清除删除元素
  31.                 current = null;
  32.                 //节点数更新
  33.                 size --;
  34.                 return oldValue;
  35.             }
  36.             //6.记录上一个节点
  37.             prev = current;
  38.             //7.当前节点下移
  39.             current = current.getNext();
  40.         }
  41.         return null;
  42.     }
5.散列的实现完整代码
  1. package com.shixinke.demo.dataStruct;
  3. public class MyHashMap<K,V> {
  4.     /**
  5.      * 散列表的大小
  6.      */
  7.     private int size;
  9.     /**
  10.      * 散列表存储节点的数组
  11.      */
  12.     private Node<K, V>[] nodes;
  14.     /**
  15.      * 容量
  16.      */
  17.     private int capacity;
  18.     /**
  19.      * 默认的容量
  20.      */
  21.     private static final int DEFAULT_CAPACITY = 5;
  23.     /**
  24.      * 不带参数的初始化，使用默认容量
  25.      */
  26.     public MyHashMap() {
  27.         this.capacity = DEFAULT_CAPACITY;
  28.         clearMap();
  29.     }
  31.     /**
  32.      * 指定容量初始化
  33.      * @param capacity
  34.      */
  35.     public MyHashMap(int capacity) {
  36.         if (capacity > DEFAULT_CAPACITY) {
  37.             this.capacity = capacity;
  38.         } else {
  39.             this.capacity = DEFAULT_CAPACITY;
  40.         }
  41.         clearMap();
  42.     }
  44.     /**
  45.      * 清除占用的空间
  46.      */
  47.     public void clear() {
  48.         clearMap();
  49.     }
  51.     public void clearMap() {
  52.         this.size = 0;
  53.         this.nodes = new Node[this.capacity];
  54.     }
  56.     /**
  57.      * 添加元素
  58.      * @param key
  59.      * @param value
  60.      * @return
  61.      */
  62.     public boolean add(K key, V value) {
  63.         return put(key, value);
  64.     }
  66.     /**
  67.      * 添加元素
  68.      * @param key
  69.      * @param value
  70.      * @return
  71.      */
  72.     public boolean put(K key, V value) {
  73.         //1.新添加一个节点
  74.         Node<K, V> node = new Node<K, V>(key, value, null);
  75.         //2.计算出节点存储到数组中的位置
  76.         int index = getIndex(node.getHashCode());
  77.         //3.查找存储的位置上的节点
  78.         Node<K, V> indexNode = (Node<K, V>) nodes[index];
  79.         //4.定义一个是否为新节点的标识(默认为新增节点)
  80.         boolean newNode = true;
  81.         //5.如果插入的位置上节点不存在，那么直接将新增节点放入这个位置即可
  82.         if (indexNode == null) {
  83.             nodes[index] = node;
  84.         } else {
  85.             //否则说明该位置上有其他节点，定义一个当前指针　
  86.             Node<K, V> current = indexNode;
  87.             //6.如果当前节点的下一个节点不为null，即这个位置有不少于2个节点的数据，一直遍历
  88.             while (current.getNext() != null) {
  89.                 //7.如果插入的键已经存在　
  90.                 if (key.equals(current.getKey())) {
  91.                     //插入的值存在的话，那么修改它的值，并且将newNode设置为false,即不是新增节点
  92.                     current.setValue(value);
  93.                     newNode = false;
  94.                     break;
  95.                 }
  96.                 current = current.getNext();
  97.             }
  98.             //8.如果是新增节点，设置最后一个节点的next为新增的节点
  99.             if (newNode) {
  100.                 current.setNext(node);
  101.             }
  102.         }
  103.         //9.如果是新增节点，则更新表节点的长度
  104.         if (newNode) {
  105.             this.size ++;
  106.         }
  107.         return true;
  108.     }
  110.     /**
  111.      * 获取元素值
  112.      * @param k
  113.      * @return
  114.      */
  115.     public V get(K k) {
  116.         //1.获取键对应的索引位置
  117.         int index = getIndex(k.hashCode());
  118.         //2.获取该位置的节点
  119.         Node<K, V> node = nodes[index];
  120.         if (node != null) {
  121.             Node<K, V> current = node;
  122.             //遍历包含节点在内的链表，一直查找到与key相等的节点
  123.             while (current != null) {
  124.                 if (k.equals(current.getKey())) {
  125.                     return current.getValue();
  126.                 }
  127.                 current = current.getNext();
  128.             }
  129.         }
  130.         return null;
  131.     }
  133.     /**
  134.      * 删除某个key对应的元素
  135.      * @param key
  136.      * @return
  137.      */
  138.     public V remove(K key) {
  139.         //1.通过key获取在数组中的存储位置
  140.         int index = getIndex(key.hashCode());
  141.         //2.通过位置获取节点
  142.         Node<K, V> current = nodes[index];
  143.         //3.如果不存在，直接返回
  144.         if (current == null) {
  145.             return null;
  146.         }
  147.         //4.定义删除节点的前一个节点
  148.         Node<K, V> prev = null;
  149.         while (current != null) {
  150.             //5.如果查找到key对应的节点
  151.             if (current.getKey().equals(key)) {
  152.                 //获取原值
  153.                 V oldValue = current.getValue();
  154.                 //如果上一个节点不为null，即删除的节点不是所在位置的第一个元素
  155.                 if (prev != null) {
  156.                     //设置前一个节点的next指向删除元素的下一个元素
  157.                     prev.setNext(current.getNext());
  158.                 } else {
  159.                     //将数组对应的位置设置为当前元素的上一个元素(因为第一个元素已经被删除了，所以要更新数组中的对应的元素)
  160.                     nodes[index] = current.getNext();
  161.                 }
  162.                 //清除删除元素
  163.                 current = null;
  164.                 //节点数更新
  165.                 size --;
  166.                 return oldValue;
  167.             }
  168.             //6.记录上一个节点
  169.             prev = current;
  170.             //7.当前节点下移
  171.             current = current.getNext();
  172.         }
  173.         return null;
  174.     }
  176.     /**
  177.      * 获取表的长度
  178.      * @return
  179.      */
  180.     public int size() {
  181.         return size;
  182.     }
  184.     /**
  185.      * 是否为空
  186.      * @return
  187.      */
  188.     public boolean isEmpty() {
  189.         return size() == 0;
  190.     }
  192.     /**
  193.      * 是否包含某个key
  194.      * @param key
  195.      * @return
  196.      */
  197.     public boolean containsKey(K key) {
  198.         //1.通过键获取键存储的位置　
  199.         int index = getIndex(key.hashCode());
  200.         //2.通过索引查找到在数组中的节点
  201.         Node<K, V> current = nodes[index];
  202.         //3.如果位置上的节点为null，即不存在，直接返回
  203.         if (current == null) {
  204.             return false;
  205.         }
  206.         //4.遍历比较key与链表中的key是否一致
  207.         while (current != null) {
  208.             if (current.getKey().equals(key)) {
  209.                 return true;
  210.             }
  211.             current = current.getNext();
  212.         }
  213.         return false;
  214.     }
  216.     /**
  217.      * 打印散列表数据
  218.      */
  219.     public void print() {
  220.         Node<K, V> p = null;
  221.         System.out.print("{");
  222.         for (int i = 0; i < nodes.length; i++) {
  223.             p = nodes[i];
  224.             while ( p != null) {
  225.                 System.out.print("["+i+"]:"+p.getKey()+"="+p.getValue()+",");
  226.                 p = p.getNext();
  227.             }
  228.         }
  229.         System.out.println("}");
  230.     }
  232.     /**
  233.      * 获取某个值在数组中的对应的索引
  234.      * @param hashCode
  235.      * @return
  236.      */
  237.     private int getIndex(int hashCode) {
  238.         return hashCode % this.capacity;
  239.     }
  242.     /**
  243.      * 散列表节点
  244.      * @param <K>
  245.      * @param <V>
  246.      */
  247.     private class Node<K, V> {
  248.         //键
  249.         private K key;
  250.         //值
  251.         private V value;
  252.         //键对应的hash码
  253.         private int hashCode;
  254.         //当前键的下一个节点
  255.         private Node<K, V> next;
  257.         public Node(K key, V value, Node<K, V> next) {
  258.             this.key = key;
  259.             this.value = value;
  260.             this.hashCode = key.hashCode();
  261.             this.next = next;
  262.         }
  264.         public K getKey() {
  265.             return key;
  266.         }
  268.         public V getValue() {
  269.             return value;
  270.         }
  272.         public int getHashCode() {
  273.             return hashCode;
  274.         }
  276.         public void setValue(V value) {
  277.             this.value = value;
  278.         }
  280.         public void setNext(Node<K, V> next) {
  281.             this.next = next;
  282.         }
  284.         public Node<K, V> getNext() {
  285.             return next;
  286.         }
  288.     }
  289. }
6.例子
  1. MyHashMap<String, Integer> testMap = new MyHashMap<>(3);
  2. testMap.put("A", 1);
  3. testMap.put("B", 2);
  4. testMap.put("C", 3);
  5. testMap.put("D", 4);
  6. testMap.put("E", 5);
  7. testMap.put("F", 6);
  8. testMap.put("G", 7);
  9. testMap.print();                 //{[0]:A=1,[0]:F=6,[1]:B=2,[1]:G=7,[2]:C=3,[3]:D=4,[4]:E=5,}
  10. System.out.println(testMap.containsKey("F"));  //true
  11. System.out.println(testMap.get("F"));          //6
  12. testMap.remove("F");
  13. testMap.print();                //{[0]:A=1,[1]:B=2,[1]:G=7,[2]:C=3,[3]:D=4,[4]:E=5,}
  14. testMap.remove("E");
  15. testMap.print();                //{[0]:A=1,[1]:B=2,[1]:G=7,[2]:C=3,[3]:D=4,}

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开