Java的顺序表与散列表

Question

结合Java语言与数据结构学科内容，利用Java语言实现数据结构中的顺序表（ArrayList）与散列表（Hashmap），这两种数据结构能够对数据进行存取、删减等操作。
程序功能要求：
1.实现的两种数据结构应该能够对数据进行存取、删除操作；
2.程序应当包含去重功能，当有重复的数据添加时应当覆盖原有的数据；
3.除基本存取功能外，还应当能够进行迭代遍历；
4.程序能够进行查找操作，传入一个已有的数据参数能够返回对应的位置（仅ArrayList需要）；

Answer 1

都自定义实现了，望采纳！
散列表

package algorithm;

import java.util.Arrays;

/**
 * @author jiangnanmax
 * @email [e-mail]
 * @description HashMap
 * @date 2021/5/14
 **/

public class HashMap<K, V> {

    /**
     * 默认的初始化大小，这里设置为16
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * 默认的扩容因子，这里设置为0.75
     */
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private Entry<K, V>[] table;

    final float loadFactor;

    private int size = 0;
    private int use = 0;

    /**
     * 默认初始化方法，使用默认的CAPACITY和扩容因子
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    /**
     * 指定CAPACITY的初始化方法，使用默认的扩容因子
     *
     * @param initCapacity
     */
    public HashMap(int initCapacity) {
        this(initCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 指定CAPACITY和扩容因子的初始化方法
     *
     * @param initCapacity
     * @param loadFactor
     */
    public HashMap(int initCapacity, float loadFactor) {
        this.table = new Entry[initCapacity];
        this.loadFactor = loadFactor;
    }

    /**
     * 添加键值对，已存在的键会被新值覆盖
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        int index = hash(key);
        Entry<K, V> e = table[index];
        if (e == null) {
            table[index] = new Entry<>(key, value, null);
            size++;
            use++;
            if (use >= table.length * loadFactor) {
                resize();
            }
        } else {
            for (; e != null; e = e.next) {
                K k = e.key;
                if (k.equals(key)) {
                    e.value = value;
                    return ;
                }
            }
            Entry<K, V> tmp = table[index];
            Entry<K, V> newEntry = new Entry<K, V>(key, value, tmp);
            table[index] = newEntry;
            size++;
        }
    }

    /**
     * 获取键相应的值
     *
     * @param key
     * @return
     */
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> e = table[index];
        for (; e != null; e = e.next) {
            K k = e.key;
            if (k.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

    /**
     * 删除某一个键值对
     *
     * @param key
     */
    public void remove(K key) {
        int index = hash(key);
        Entry<K, V> e = table[index];
        Entry<K, V> pre = null;
        for (; e != null; pre = e, e = e.next) {
            K k = e.key;
            if (k.equals(key)) {
                if (pre == null) {
                    table[index] = e.next;
                } else {
                    pre.next = e.next;
                }
                size--;
                return ;
            }
        }
    }

    /**
     * 存在性判断
     *
     * @param key
     * @return
     */
    public boolean contains(K key) {
        int index = hash(key);
        Entry<K, V> e = table[index];
        for (; e != null; e = e.next) {
            if (e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 清空
     */
    public void clear() {
        Arrays.fill(table, null);
        size = 0;
        use = 0;
    }

    /**
     * 获取当前容器中的元素个数
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 判空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 计算键的对应slot
     *
     * @param key
     * @return
     */
    private int hash(K key) {
        int hashCode = Math.abs(key.hashCode());
        hashCode %= table.length;
        return hashCode;
    }

    /**
     * 扩容
     */
    private void resize() {
        int newLength = table.length << 1;
        Entry<K, V>[] oldTable = table;
        table = new Entry[newLength];
        use = 0;
        for (int i = 0; i < oldTable.length; i++) {
            Entry<K, V> e = oldTable[i];
            for (; e != null; e = e.next) {
                int index = hash(e.key);
                if (table[index] == null) {
                    table[index] = new Entry<>(e.key, e.value, null);
                    use++;
                } else {
                    Entry<K, V> newEntry = new Entry<>(e.key, e.value, table[index]);
                    table[index] = newEntry;
                }
            }
        }
    }

    static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

}

用法

public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>(2);
        map.put("name", "jiangnanmax");
        map.put("age", "**");
        map.put("blog", "https://jiangnanmax.blog.csdn.net/");
        map.put("ecnu", "cs");
        map.put("ecnu", "dase");

        System.out.println(map.get("name"));
        System.out.println(map.get("ecnu"));
        System.out.println(map.size());
        System.out.println(map.contains("age"));
        map.remove("age");
        System.out.println(map.contains("age"));
    }

/**
输出：

jiangnanmax
dase
4
true
false

 */