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的方案更复杂,而且只能缓解击穿,不能避免,唯一的优势就是缓存会过期,能节省一部分缓存服务的使用空间。

InnoDB 聚集索引和非聚集索引

区别

聚集索引包含所需的所有数据,比如mysql整张表就是一个聚集索引
比如索引的key就是主键,值就是这一行的所有字段,根据主键查询时可以直接查到所有字段

非聚集索引不包含所有数据,但会包含聚集索引的key
比如索引的key是两个自定义的字段,而值就是主键,根据这两个字段,只能直接查出主键是什么,所以这时如果想查询其它字段的值还会通过主键去聚集索引中再查询一次(即回表)。

覆盖索引减少回表

如果查询的条件或结果中,只使用了非聚集索引定义中的那几个字段的话,就不会回表二次查询。
比如索引是uid, username两个字段:
执行SELECT status WHERE uid = ?时会回表二次查询status是什么
但执行SELECT username WHERE uid = ?时就不会二次查询,因为username在索引定义中。

如何创建聚集索引

聚集索引只是存储方式,不是索引类型,所以在创建索引时无法指定是否是聚集索引。

默认情况下会根据主键创建聚集索引。
如果没有主键,会根据第一个唯一索引创建聚集索引。
如果也没有唯一索引,会使用row id做聚集索引。

延伸:MyISAM

MyISAM中即使是聚集索引节点中也不包含数据,而是数据在硬盘的物理地址。而非聚集索引同样存的也是物理地址,所以没有回表问题。这么来看MyISAM好像比InnoDB快。但是因为MyISAM的节点上没有存储数据,所以数据在磁盘上有可能不是连续顺序存储的(按插入时间写入),那么在按范围查询的时候是不是会增加磁盘读取次数。

B树和B+树的区别

B树中的元素不会出现重复的,元素有可能在中间节点也有可能在叶子节点。
B+树中所有元素都会出现在叶子节点,但也有可能同时出现在中间节点。B+树叶子节点间有额外的链表结构。
这两点会让B+树在按连续的范围查找时比B树更快。
另外B树在查找时不同的元素因为在不同层级的节点,所以不同的元素查询时间可能有差异,而B+树所有的元素都在叶子节点所以查询的时间更平均一些

B树每个元素都包含卫星数据。
B+树只有叶子节点中的元素包含卫星数据。
这会使在中间节点的页大小相同的情况下B+树能比B树存更多的节点,也就意味着B+树有可能比B树更矮一些(树的高度决定磁盘io次数,越矮次数越少)

解决git的error: cannot lock ref问题

今天更新代码时出现了这个错误信息

error: cannot lock ref 'refs/remotes/origin/xxxx/log': 'refs/remotes/origin/xxxx' exists; cannot create 'refs/remotes/origin/xxxx/log'
From ssh://ssh.gitlab.oooo.com:22/MyGroup/composer
 ! [new branch]      xxxx/log -> origin/xxxx/log  (unable to update local ref)

出现这个问题的原因是,之前远程有一个xxxx分支,后来别人删掉远端了xxxx分支,又建了一个xxxx/log分支,但是本地还有xxxx的信息。这样就出现了git分支名冲突的问题,类似于文件系统中一个路径不可能既是文件又是目录。

这时需要执行这条命令:

git update-ref -d refs/remotes/origin/xxxx

单独更新一下本地的xxxx信息

nginx+fpm+upstream调优

最近发现服务器经常出现502的问题,但是并发量并没有达到那么高(fpm设置了500个进程)。看了一下nginx的配置

upstream fastcgi_backend {
    server 127.0.0.1:9000;
    server 127.0.0.2:9000;
    server 127.0.0.3:9000;
    server 127.0.0.4:9000;
}

4个IP的问题,问了运维,说是为了增加可以支撑连接数,但实际上这四个IP都是本地的fpm(我感觉这波优化没什么卵用)fpm总共500个,端口也能即时回收,所以应该也不是端口沾满的问题。

后来看日志,发现有一些timeout的请求,而且每一波502的请求附近都会有一些504,但是504也不算太多,不会将所有的fpm进程都占满。

看了nginx的文档后发现如果一个server无法处理响应了,会使用其它的server重试,并且多次无法处理响应(默认1次),nginx会临时将这个节点摘掉(默认10秒)。而fpm超时就被nginx认为是无法处理响应了,这时理论上会重试4次(相当于放大了问题)。

这就意味着如果10秒内有4个请求造成了fpm超时就会造成500个fpm进程都被认为是不可用。

优化程序是一种方案(正常来说不应该这么慢)。另外也可以优化一下nginx的配置

upstream fastcgi_backend {
    server 127.0.0.1:9000 max_fails=0 fail_timeout=0;
}

鉴于我对4个IP的不认同,我将IP改回了一个。并且设置mx_fails=0即无论fpm是否可用都将请求转发至fpm,我觉得这样也没什么问题,如果fpm真的挂了,nginx应该也能处理。fail_timeout是一个无关紧要的参数,即如果服务挂了临时摘掉多少秒,因为mx_fails=0,所以这个参数设不设都可以。

最后/usr/local/openresty/nginx/sbin/nginx -t校验,/usr/local/openresty/nginx/sbin/nginx -s reload重新加载配置,问题解决。

启动和停止服务脚本

约定

  • /opt/start.sh :通用启动脚本,第一个参数指定应用名,如/opt/start.sh myapp
  • /opt/stop.sh :通用停止脚本,第一个参数指定应用名,如/opt/stop.sh myapp
  • /opt/<app_name>/<app_name>.jar :启动的应用jar包
  • /opt/<app_name>/<app_name>.pid :启动后的进程id,由start.sh自动生成
  • /opt/<app_name>/log/stdout.log :应用的标准输出,由start.sh自动生成
  • /opt/<app_name>/log/stderr.log :应用的错误输出,由start.sh自动生成
  • /opt/<app_name>.runuser :当以root运行start.sh时,应用的运行用户,如果没有这个文件将以root运行

启动脚本(start.sh)

#!/bin/bash
APP_NAME=$1
BASE_DIR=$(readlink -f $(dirname "$0"))
APP_DIR=${BASE_DIR}/${APP_NAME}
JAR_FILE=${APP_DIR}/${APP_NAME}.jar
PID_FILE=${APP_DIR}/${APP_NAME}.pid
LOG_DIR=${APP_DIR}/log
RUN_USER_FILE="${BASE_DIR}/${APP_NAME}.runuser"

RUN() {
    if [ ${RUN_USER} ]; then
        SCRIPT="[email protected]"
        return $(runuser -l ${RUN_USER} -c "${SCRIPT}" 2>/dev/null)
    else
        return [email protected]
    fi
}

if [ ! ${APP_NAME} ]; then
    echo "App name not found!";
    exit 1;
fi

if [ ! -f ${JAR_FILE} ]; then
    echo "Jar file not found: ${JAR_FILE}";
    exit 1;
fi

if [ -f ${PID_FILE} ]; then
    echo "App is running!: $(cat ${PID_FILE})";
    exit 1;
fi

RUN_USER=$(whoami)
if [ ${RUN_USER} == 'root' ]; then
    if [ -f ${RUN_USER_FILE} ]; then
        RUN_USER=$(cat ${RUN_USER_FILE});
    fi
else
    RUN_USER=''
fi

if [ ! -d ${LOG_DIR} ]; then
    if ! RUN "mkdir ${LOG_DIR}"; then
        echo "Start failed: can not create log directory.";
        exit 1;
    fi
fi

cd ${APP_DIR};
if ! RUN "nohup java -jar ${JAR_FILE} > ${LOG_DIR}/stdout.log 2>${LOG_DIR}/stderr.log & echo \$! > ${PID_FILE}" ; then
    echo "Start failed: run failed!";
    exit 1;
fi

echo "Started: ${JAR_FILE}";

停止脚本(stop.sh)

#!/bin/bash
APP_NAME=$1
BASE_DIR=$(dirname "$0")/${APP_NAME}
PID_FILE=${BASE_DIR}/${APP_NAME}.pid
if [ ! ${APP_NAME} ]; then
    echo "App name not found!";
    exit 1;
fi

if [ -f ${PID_FILE} ]; then
    PID=$(cat ${PID_FILE});
    echo kill ${PID}
    kill ${PID};
    rm -f ${PID_FILE};
else
    echo "Not running...";
fi
exit 0;

ubuntu服务器初始化脚本

最近买了几台云主机,写了个脚本初始化用户和权限

  1. 创建一个无密码的新用户
  2. 开启SSH登录
  3. 设为SUDOUser
  4. 禁用root用户
#!/bin/bash
NEWUSER='fyn'
IDRSA_PUB="*****"
useradd -m ${NEWUSER}
mkdir /home/${NEWUSER}/.ssh
echo ${IDRSA_PUB} > /home/${NEWUSER}/.ssh/authorized_keys
chown ${NEWUSER}:${NEWUSER} -R /home/${NEWUSER}
chmod 0600 /home/${NEWUSER}/.ssh/authorized_keys
echo -e "\n${NEWUSER} ALL=(ALL) NOPASSWD:ALL" >> /etc/sudoers
chsh -s /bin/bash ${NEWUSER}
echo -e "\n127.0.0.1 $(hostname)" >> /etc/hosts
passwd -l root

nginx反向代理426

nginx反向代理默认用的http1.0,如果尚有不支持http1.0,需要增加proxy_http_version 1.1选项来指定版本

location /api {
    proxy_http_version 1.1;
    proxy_pass http://192.168.1.30:8080/;
}