Java DataStructure-Map

HashMap

HashMap底层实现采用了哈希表，这是一种非常重要的数据结构。对于我们以后理解很多技术都非常有帮助（比如：redis数据库的核心技术和HashMap一样），因此，非常有必要去理解。
数据结构中由数姐和链表来实现对数据的存储，他们各有特点。
（1）数组：占用空间连续。寻址容易，查询速度快。但是，增加和制除效率非常低。
（2）链表：占用空间不连续。寻址困难，查询速度慢，但是，增加和制除效率非常高。
结合其优点便衍生出了哈希表，哈希表的本质就是“数组+链表”。

自Java 1.2以来，HashMap是Java集合的一部分。它提供了Java Map接口的基本实现。它以（键，值）对存储数据。要访问一个值，必须知道其键。 HashMap之所以被称为HashMap，因为它使用了一种称为Hashing(散列)的技术。Hashing(散列)是一种将大字符串转换为代表相同字符串的小字符串的技术，较短的值有助于索引编制和更快的搜索。

常用方法：

方法详解

HashMap源码学习01
HashMap源码学习02

代码实现：

package DataStructure;

import java.util.HashMap;
import java.util.Map;

public class MapDemo {
    public static void main(String[] args) {
        Map<Integer, String> m1 = new HashMap<>();
        // Map中的常用方法
        m1.put(1, "a");
        m1.put(2, "b");
        m1.put(3, "c");
        System.out.println(m1.get(1));  // 通过键来查找获取键值
        System.out.println(m1.size());  // 获取Map的大小
        System.out.println(m1.isEmpty()); // 判断Map是否为空
        System.out.println(m1.containsKey(2)); // 判断Map中是否包含某个键
        System.out.println(m1.containsValue("")); // 判断Map中是否包含某个键值

        Map<Integer, String> m2 = new HashMap<>();
        m2.put(4, "w");
        m2.put(5, "x");
        m1.putAll(m2);  // 将m2中的内容添加到m1中
        System.out.println("添加m2后:" + m1);
        // Map中键不能重复！如果重复(是否重复是通过equals()方法来判断的)，则新的会覆盖旧的！
        m1.put(3, "x");
        System.out.println(m1);
    }
}

演示结果：

a
3
false
true
false
添加m2后:{1=a, 2=b, 3=c, 4=w, 5=x}
{1=a, 2=b, 3=x, 4=w, 5=x}

手动实现HashMap

目前实现有： put() , get() , toString() 方法

代码：

public class Nodex<K,V> {
    int hash;
    K key;
    V value;
    Nodex next;
}

/**
 * 自定义一个HashMap
 */

public class SxtHashMap01<K,V> {
    Nodex[] table;  // 位桶数组，bucket array
    int size;       // 存放的键值对的个数

    public SxtHashMap01() {
        table = new Nodex[16];  // 构造一个长度为16，存放Nodex的 table，其中长度一般定义为2的整次幂
    }

    // get方法
    public V get(K key) {
        int hash = myHash(key.hashCode(),table.length);
        V value = null;
        if(table[hash] != null) {
             Nodex temp = table[hash];
             while (temp != null) {
                 if(temp.key.equals(key)){
                     value = (V) temp.value;
                     break;
                 }else {
                     temp = temp.next;
                 }
             }
        }
        return value;
    }

    // put方法
    public void put(K key, V value) {

        // 如果还要完善还需要考虑数组扩容的问题，学习相关内容后再弄！

        // 定义一个新的节点对象
        Nodex newNode = new Nodex();
        newNode.hash = myHash(key.hashCode(), table.length);
        newNode.key = key;
        newNode.value = value;
        newNode.next = null;

        Nodex temp = table[newNode.hash];
        Nodex itsLast = null;       // 用与存储遍历时的最后一个元素
        boolean keyRepeat = false;
        if (temp == null) {
            // 如果此处数组为空，则将新的节点放入
            table[newNode.hash] = newNode;
            size++;
        } else {
            // 如果此处不为空，则遍历对应的链表
            while (temp != null) {
                // 如果key值重复则覆盖
                if (temp.key.equals(key)) {
//                    System.out.println("key值重复！");
                    keyRepeat = true;
                    temp.value = value;     // 覆盖value值，其他值保持不变
                    break;
                } else {
                    // 如果key值不重复，则遍历下一个
                    itsLast = temp;
                    temp = temp.next;
                }
            }
            if (!keyRepeat) {
                itsLast.next = newNode;
                size++;
            }
        }
    }

    public int myHash(int k, int length) {
//        System.out.println("hash in myHash is (%):" + (k % (length - 1)));
//        System.out.println("hash in myHash is (&):" + (k & (length - 1)));
        return k & (length - 1);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Nodex:{");
        for(int i = 0; i < table.length; i++) {
            Nodex temp = table[i];
            while(temp != null) {
                sb.append(temp.key + ":" + temp.value + ",");
                temp = temp.next;
            }
        }
        sb.setCharAt(sb.length()-1,'}');
        return sb.toString();
    }



    public static void main(String[] args) {
        SxtHashMap01<Integer,String > sx = new SxtHashMap01<>();
        sx.put(10, "aa");
        sx.put(20, "bb");
        sx.put(30, "cc");
        sx.put(20,"ssss");
        // 53,69,85 的hash值都为5，测试
        sx.put(53,"ff");
        sx.put(69,"dd");
        sx.put(85,"ee");
        System.out.println(sx.toString());

        System.out.println(sx.get(53));
    }
}