【算法】【算法杂谈】具有setall功能的hash表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】【算法杂谈】具有setall功能的hash表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
纳管一个hashmap，增强hashmap的功能，使其具有能够立刻将当前hash表中的所有值都变成统一的值的能力
具体来讲，就是如果当前使用了setall的功能，那么当前的表中再获取所有的key对应的值都是setall所设置的值了。

解决方案

原问题：
解法很简单，增加“时间戳”
1、首先如果使用真的时间戳可以做到setall的功能，但是时间戳占用了64位，所以没有必须要使用这么大的内存，所以这里使用了int类型直接存储类似于时间戳的东西
2、首先数据结构类中的变量如代码编写中所示
3、setall功能：首先正常放入hashmap流程不用说，time++后赋值给time变量，并将value赋值给myvalue引用
4、get功能：获取时需要先判断是否存在key，如果存在则取出值后获取到time值判断是否在time之前加入，如果是，则返回myvalue变量即可。

代码编写

java语言版本

原问题：
方法一:

public class SetAllHashMapCp1<K, V> {

    /**
     * 维护一个hash用来存储数据
     */
    private Map<K, MyValue<V>> map;

    /**
     * 模拟时间戳
     * 只要当前存在值进来，就增加1,删除值不会减少
     */
    private Long time;

    /**
     * setall操作值
     */
    private MyValue<V> setAllValue;


    public SetAllHashMapCp1() {
        this.time = 0L;
        this.map = new HashMap<>(16);
    }

    /**
     * put操作
     * 正常put操作，增加一个时间戳就行了
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        this.map.put(key, new MyValue<>(this.time++, value));
    }


    /**
     * get操作
     * 取得时候需要比较一下setall的时间戳
     * 如果在时间戳前面，则返回setall的值
     * 如果在后面则返回原值
     * be careful null value!
     * @param key
     * @return
     */
    public V get(K key) {
        if (!isContainsKey(key)) {
            return null;
        }
        MyValue<V> vMyValue = map.get(key);
        return this.setAllValue == null
                || vMyValue.getTime() > this.setAllValue.getTime() ? vMyValue.getValue() : this.setAllValue.getValue();
    }

    /**
     * Provide a normal getting operation
     * @param key
     * @return
     */
    public V nomalGet(K key) {
        MyValue<V> vMyValue = map.get(key);
        return vMyValue == null ? null : vMyValue.getValue();
    }


    /**
     * 是否存在该key
     * @param key
     * @return
     */
    public boolean isContainsKey(K key) {
        return map.containsKey(key);
    }

    /**
     * setall功能
     * @param value
     */
    public void setAll(V value) {
        this.setAllValue = new MyValue<>(this.time++, value);
    }


    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
        SetAllHashMapCp1<String, String> mapCp1 = new SetAllHashMapCp1<>();
        mapCp1.put("1", "!!");
        mapCp1.put("2", "@@");
        mapCp1.setAll("9999999");
        mapCp1.put("33", "##");
        mapCp1.put("44", "$$");
    }


    /**
     * 维护一个value和当前value所带的时间戳
     * @param <V>
     */
    private class MyValue<V> {


        private Long time;

        private V value;

        public MyValue(Long time, V value) {
            this.time = time;
            this.value = value;
        }

        public Long getTime() {
            return time;
        }

        public void setTime(Long time) {
            this.time = time;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }

}