命名格式转换

在做一些生成代码或生成配置时经常会遇到命名格式不一样的问题,比如有的地方要用驼峰命名(比如代码的类和遍历),有的地方要用下划线命名(比如数据库字段)。因此写了个小工具来快速将一组单词转换成特定格式的命名。

因为我的使用场景中没有太严苛的性能要求,所以里面用到了正则,并且应该也不是最优解,所以不建议在高并发的场景用(也没做过性能测试)。

在查规范的时候学习到了一些有意思的单词,很形象的形容了命名格式。
比如下划线命名是snake,纯大写的下划线命名(比如常量定义AAA_BBB_CCC)是screaming snake(尖叫蛇)。
大驼峰是pascal(这个其实不太理解为什么是帕斯卡)。
用横线命名(比如url、域名、docker服务名:aaa-bbb-ccc)是kebab(烤肉串)。

<?php
/**
 * Created by PhpStorm.
 * User: fyn
 * Date: 2018/10/9
 * Time: 10:40 AM
 */
namespace Fyn\Common;

class StringCase
{


    /**
     * snake_case
     * @param $string
     * @return string
     */
    public static function snakeCase($string) {
        $string = lcfirst($string);
        $string = preg_replace_callback('/[A-Z]+/', function ($text) {
            return '_'.strtolower($text[0]);
        },$string);
        $string = preg_replace('/[^a-zA-Z0-9]+/','_',$string);
        return $string;
    }

    /**
     * SCREAMING_SNAKE_CASE
     * @param $string
     * @return string
     */
    public static function screamingSnakeCase($string) {
        return strtoupper(self::snakeCase($string));
    }

    /**
     * kebab-case
     * @param $string
     * @return string
     */
    public static function kebabCase($string) {
        return str_replace('_','-',self::snakeCase($string));
    }

    /**
     * PascalCase
     * @param $string
     * @return string
     */
    public static function pascalCase($string) {
        $arr = preg_split('/[^a-zA-Z0-9]/', $string);
        $string = implode('',array_map('ucfirst',$arr));
        return $string;
    }

    /**
     * camelCase
     * @param $string
     * @return string
     */
    public static function camelCase($string) {
        return lcfirst(self::pascalCase($string));
    }

    /**
     * htmlcase
     * @param $string
     * @return string
     */
    public static function htmlCase($string) {
        return strtolower(preg_replace('/[^a-zA-Z0-9]+/','', $string));
    }
}

使用方法:

use Fyn\Common\StringCase;

echo StringCase::snakeCase("This_is A-test@text"),"\n";  //this_is_a_test_text

echo StringCase::kebabCase("This_is A-test@text"),"\n";  //this-is-a-test-text

echo StringCase::pascalCase("This_is A-test@text"),"\n"; //ThisIsATestText

echo StringCase::camelCase("This_is A-test@text"),"\n";  //thisIsATestText

HashMap的原理与简单实现

数组

HashMap底层本质上是一个固定长度的数组

根据Key定位到数组

HashMap的“hash”其实就是对key做哈希,比如将所有字符的charCode加起来然后再除以数组长度后取模(只是举个简单的例子,比一定要用这种算法,无论用那种算法,都会尽量保证当key足够多时,哈希后的结果能正态分布)。这样无论传什么key最终都会被转换成某一个数组下标,并且相同的key两次调用时获得的数组下标肯定是一样的。

class HashMap {

    /** @type {*[]} */
    _array = [];
    /** @type {number} */
    _size = 0;

    constructor(size = 8) {
        if (size < 1) {
            throw new Error("size error")
        }
        this._size = size;
        this._array = new Array(size);
        this._array.fill(null);
    }

    put(key, value) {
        const index = this._hashCode(key);
        this._array[index] = value;
    }

    get(key) {
        const index = this._hashCode(key);
        return this._array[index];
    }

    _hashCode(str) {
        //这里只是举个简单的例子,将所有的字符相加得出一个数字再取模
        str = String(str);
        let n = 0;
        let i = str.length - 1;
        while (i--) {
            n += str.charCodeAt(i);
        }
        return n % this._size;
    }
}

处理碰撞的问题

由于数组的长度是固定的,当key足够多的时候会出现两个key共用同一个数组下标的问题,比如长度为8的map,如果key为9或17最终都会定位到数组下标为1的位置上。这时就要引入单向链表的逻辑。
当往数组中存数据时,除了将value存进去还要将原始的key也存进去,同时要加一个next字段,如果发生了碰撞,第二个key不会直接存到数组里,而是将之前那条数据的next指向它。
当查询时获取到数组下标后先从数组中取到数据,然后再判断原始key和传进来的key是否一致,如果不一致再判断next的key是否一致,直到找到一致的或没有next

class HashMap {

    /** @type {HashMap.HashMapEntity[]} */
    _array = [];
    /** @type {number} */
    _size = 0;
    /** @type {number} map中的key数量 */
    length = 0;

    constructor(size = 8) {/*...*/}

    put(key, value) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        if (entity === null) {
            //数组中这个位置是空的
            this._array[index] = new HashMap.HashMapEntity(key, value);
        } else {
            //数组中这个位置已经有东西了
            do {
                if (entity.key === key) {
                    entity.value = value;
                    return false;//key已存在,直接更新value
                }
            } while (entity.next !== null && (entity = entity.next));
            //循环结束没有发现相同的key,则创建一个新的实体并挂到链表的末尾
            entity.next = new HashMap.HashMapEntity(key, value);
        }
        this.length++; //key不存在,添加了新值
        return true;
    }

    get(key) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        while (entity !== null) {
            if (entity.key === key) {
                return entity.value;
            } else {
                entity = entity.next;
            }
        }
        return undefined;
    }

    _hashCode(str) {/*...*/}

    static HashMapEntity = class {

        /** @type {string} */
        key;

        /** @type {HashMap.HashMapEntity} */
        next = null;

        /** @type {*} */
        value;

        constructor(key, data) {
            this.key = key;
            this.value = data;
        }
    }
}

效率与扩容

如果数组的长度很小,但是插入的key很多,这时就会出现大量的碰撞,虽然通过链表解决了这个问题,但是当链表长度很长时,插入和查询都会很慢,因为每次都要从链表的头开始查,最倒霉的情况要遍历整个链表才知道是否存在。
这时我们可以对数组进行扩容,这样碰撞的概率就会小很多。
因为扩容后数组的长度发生了改变,因此原有的哈希值对应的数组下标也有可能发生改变。比如数组长度为8时key为9和17时都对应的数组下标1,但是当数组长度扩充到16时,key为9时对应的数组下标变成了9。
因此扩容后我们还需要重排数据。这就意味着每次扩容可能会产生很大的开销,所以java的代码规范里要求在使用HashMap时最好预判数据量在初始化时指定好数组的长度,避免在运行的过程中反复扩容。在使用其它语言开发时如果hashMap/map/dictionary之类的如果能指定初始长度,最好也可以预判一下然后设置好初始值。

class HashMap {

    /** @type {HashMap.HashMapEntity[]} */
    _array = [];
    /** @type {number} */
    _size = 0;
    /** @type {number} map中的key数量 */
    length = 0;

    constructor(size = 8) {/*...*/}

    put(key, value) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        /*...省略略中间代码...*/
        this.length++; //key不存在,添加了新值
        if(this.length > this._size * 0.75) {
            // 当数据量超过预设长度的75%时进行扩容
            this._resize();
        }
        return true;
    }

    get(key) {/*...*/}

    _hashCode(str) {/*...*/}

    _resize() {
        this.length = 0;
        const oldArray = this._array;
        // 创建新的,长度翻倍的数组
        this._size = this._size * 2; 
        this._array = new Array(this._size);
        this._array.fill(null);
        // 遍历旧数组和链表,将每一对key/value复制到新数组中
        oldArray.forEach(entity => {
            while (entity !== null) {
                this.put(entity.key, entity.value);
                entity = entity.next;
            }
        })
    }

    static HashMapEntity = class {/*...*/}
}

附:完整实现

class HashMap {

    /**
     * @type {number}
     * @private
     */
    _size;

    /**
     * @type {HashMap.HashMapEntity[]}
     * @private
     */
    _array;

    /**
     * map的长度(key的数量)
     * @type {number}
     * @private
     */
    _length = 0;

    /**
     * map的长度(key的数量)
     * @return {number}
     */
    get length(){
        return this._length;
    }

    constructor(size = 8) {
        if (size < 1) {
            throw new Error("size error")
        }
        this._size = size;
        this._array = new Array(size);
        this._array.fill(null);
    }

    /**
     * @param {string} key
     * @param {*} value
     */
    put(key, value) {
        if (this._put(key, value)) {
            if (++this._length > this._size * .75) {
                this._resize()
            }
        }
    }

    /**
     * @param {string} key
     * @param {*} value
     * @return {boolean}
     * @private
     */
    _put(key, value) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        if (entity === null) {
            this._array[index] = new HashMap.HashMapEntity(key, value);
        } else {
            do {
                if (entity.key === key) {
                    entity.value = value;
                    return false;
                }
            } while (entity.next !== null && (entity = entity.next));
            entity.next = new HashMap.HashMapEntity(key, value);
        }
        return true;
    }

    /**
     *
     * @param {string} key
     * @return {*}
     */
    get(key) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        while (entity !== null) {
            if (entity.key === key) {
                return entity.value;
            } else {
                entity = entity.next;
            }
        }
        return undefined;
    }

    /**
     *
     * @param {string} key
     * @return {boolean}
     */
    keyExists(key) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        while (entity !== null) {
            if (entity.key === key) {
                return true;
            } else {
                entity = entity.next;
            }
        }
        return false;
    }

    /**
     *
     * @param {string} key
     * @return {boolean}
     */
    delete(key) {
        const index = this._hashCode(key);
        /** @type {HashMap.HashMapEntity} */
        let current = this._array[index];
        /** @type {HashMap.HashMapEntity} */
        let prev = null;
        while (current !== null) {
            if (current.key === key) {
                if (prev === null) {
                    if (current.next !== null) {
                        this._array[index] = current.next;
                    } else {
                        this._array[index] = null;
                    }
                } else {
                    prev.next = current.next
                }
                this._length--;
                return true;
            } else {
                prev = current;
                current = current.next;
            }
        }
        return false;
    }

    /**
     * 数组扩容
     * @private
     */
    _resize() {
        const oldArray = this._array;
        this._size <<= 1;
        this._array = new Array(this._size);
        this._array.fill(null);
        oldArray.forEach(entity => {
            while (entity !== null) {
                this._put(entity.key, entity.value);
                entity = entity.next;
            }
        })
    }

    /**
     * 计算哈希值
     * @param {string} str
     * @return {number}
     * @private
     */
    _hashCode(str) {
        str = String(str);
        let n = 0;
        let i = str.length - 1;
        while (i--) {
            n += str.charCodeAt(i);
        }
        return n % this._size;
    }

    static HashMapEntity = class {
        /**
         * @type {string}
         */
        key;

        /**
         * @type {HashMap.HashMapEntity}
         */
        next = null;

        /**
         * @type {*}
         */
        value;

        constructor(key, data) {
            this.key = key;
            this.value = data;
        }
    }

}

缓存穿透,缓存雪崩,缓存击穿

缓存穿透

问题:当访问一个不存在的商品id时因为没有缓存会直接查数据库,如果有高并发访问不存在的id可能导致数据库压力变大。

解决方法:可以把空值也进行缓存,但缓存时间可以相对较低

缓存雪崩

问题:如果大量商品的缓存是在同一时间生成的,比如每天零点跑脚本更新缓存,会导致1点时大量缓存同时过期,这时会出现大量数据库查询。

解决方法:可以将过期时间加上一些随机因子,比如过期时间随机设置为为45分钟至1小时15分。

缓存击穿

问题:缓存未生成或过期后,突然高并发访问。因为生成缓存需要一定的时间,所以在这段时间并发请求都认为缓存不存在都去查数据库。

解决方法1:设置不过期的缓存(在修改数据时再更新缓存)

解决方法2:在缓存的数据中也记录一个时间,但比缓存的过期时间短。比如缓存1小时,数据中记半个小时。半小时后再访问这条数据时仍然从缓存中返回数据,但是同时会往消息队列中发一条请求更新缓存的消息。然后后台任务消费消息时去更新缓存,在更新缓存前要再次检查时间,因为同一个商品并发访问时有可能发送多条消息,但是实际上去只需要更新一次缓存就够了,剩下的可以忽略。这里还涉及到消息分区的问题,因为一般会多线程消费消息队列,这时要保证同一个商品的更新请求不会出现在多个线程中。

方法2的方案更复杂,而且只能缓解击穿,不能避免,唯一的优势就是缓存会过期,能节省一部分缓存服务的使用空间。