简栈

Hash算法

Hash算法在路由算法应用中，为了保证数据均匀的分布，例如有3个桶，分别是0号桶，1号桶和2号桶；现在有12个球，怎么样才能让12个球平均分布到3个桶中呢？使用Hash算法的做法是，将12个球从0开始编号，得到这样的一个序列：0，1，2，3，4，5，6，7，8，9，10，11。将这个序列中的每个值模3，不管数字是什么，得到的结果都是0,1,2，不会超过3，将结果为0的数字放入0号桶，结果为1的数子放入1号桶，结果为2的数字放入2号桶，12个球就均匀的分布到3个桶中，0,3,6,9,12号球放入0号桶，1,4,7,10号球放入1号桶，2,5,8,11号球放入2号桶。

一致性Hash算法

一致性Hash算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点（Hot Spot）问题，初衷和CARP十分相似。一致性Hash修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。

一致性Hash算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性Hash算法是对2^32取模，什么意思呢？简单来说，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形）。整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。

特性定义

一致性Hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

**1、平衡性（Balance）：**平衡性是指哈希的结果能够尽可能分布在所有的缓冲(Cache)中去，这样可以使得所有的缓冲空间得到利用。很多哈希算法都能够满足这一条件。

**2、单调性（Monotonicity）：**单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应该能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会映射到旧的缓冲集合中的其他缓冲区。

作者：FserSuN

来源：https://blog.csdn.net/Revivedsun/article/details/71022871

LoadBalance负责从多个Invoker中选出具体的一个用于本次调用，以分摊压力。Dubbo中LoadBalance结构如下图。

1
2
3
4

com.alibaba.dubbo.rpc.cluster.LoadBalance 
接口提供了
<T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) throws RpcException; 
通过该方法，进行结点选择。

1
2
3
4

com.alibaba.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance 
实现了一些公共方法，并定义抽象方法
protected abstract <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation); 
该方法由具体的负载均衡实现类去实现。

一致性哈希负载均衡配置

具体的负载均衡实现类包括4种。分别是随机、轮训、最少活跃、一致性Hash
一致性哈希负载均衡配置

配置如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

<dubbo:service interface="..." loadbalance="consistenthash" />
或：

<dubbo:reference interface="..." loadbalance="consistenthash" />
或：

<dubbo:service interface="...">
    <dubbo:method name="..." loadbalance="consistenthash"/>
</dubbo:service>
或：

<dubbo:reference interface="...">
    <dubbo:method name="..." loadbalance="consistenthash"/>
</dubbo:reference

作者：王念博客

来源：https://my.oschina.net/wangnian/blog/3064886

前言：在工作中，谈到有小数点的加减乘除都会想到用BigDecimal来解决，但是有很多人对于double或者float为啥会丢失精度一脸茫然。还有BigDecimal是怎么解决的？话不多说，我们开始。

浮点数是啥？

浮点数是计算机用来表示小数的一种数据类型，采用科学计数法。在java中，double是双精度，64位，浮点数，默认是0.0d。float是单精度，32位.浮点数，默认是0.0f；

在内存中存储

float 符号位(1bit) 指数(8 bit) 尾数(23 bit)
double 符号位(1bit) 指数(11 bit) 尾数(52 bit)

float在内存中指数是8bit，由于阶码实际存储的是指数的移码，假设指数的真值是e,阶码为E，则有E=e+(2^n-1 -1)。其中 2^n-1 -1是IEEE754标准规定的指数偏移量，根据这个公式我们可以得到 2^8 -1=127。于是，float的指数范围为-128 +127，而double的指数范围为-1024 +1023。其中负指数决定了浮点数所能表达的绝对值最小的非零数；而正指数决定了浮点数所能表达的绝对值最大的数，也即决定了浮点数的取值范围。

float的范围为-2^128 ~ +2^127，也即-3.40E+38 ~ +3.40E+38；
double的范围为-2^1024 ~ +2^1023，也即-1.79E+308 ~ +1.79E+308

L1，L2，L3 指的都是CPU的缓存，他们比内存快，但是很昂贵，所以用作缓存，CPU查找数据的时候首先在L1，然后看L2，如果还没有，就到内存查找一些服务器还有L3 Cache，目的也是提高速度。

高速缓冲存储器Cache是位于CPU与内存之间的临时存储器，它的容量比内存小但交换速度快。在Cache中的数据是内存中的一小部分，但这一小部分是短时间内CPU即将访问的，当CPU调用大量数据时，就可避开内存直接从Cache中调用，从而加快读取速度。由此可见，在CPU中加入Cache是一种高效的解决方案，这样整个内存储器（Cache+内存）就变成了既有Cache的高速度，又有内存的大容量的存储系统了。Cache对CPU的性能影响很大，主要是因为CPU的数据交换顺序和CPU与Cache间的带宽引起的。

高速缓存的工作原理

1． 读取顺序

CPU要读取一个数据时，首先从Cache中查找，如果找到就立即读取并送给CPU处理；如果没有找到，就用相对慢的速度从内存中读取并送给CPU处理，同时把这个数据所在的数据块调入Cache中，可以使得以后对整块数据的读取都从Cache中进行，不必再调用内存。

正是这样的读取机制使CPU读取Cache的命中率非常高（大多数CPU可达90%左右），也就是说CPU下一次要读取的数据90%都在Cache中，只有大约10%需要从内存读取。这大大节省了CPU直接读取内存的时间，也使CPU读取数据时基本无需等待。总的来说，CPU读取数据的顺序是先Cache后内存。

2． 缓存分类

前面是把Cache作为一个整体来考虑的，现在要分类分析了。Intel从Pentium开始将Cache分开，通常分为一级高速缓存L1和二级高速缓存L2。

在以往的观念中，L1 Cache是集成在CPU中的，被称为片内Cache。在L1中还分数据Cache（I-Cache）和指令Cache（D-Cache）。它们分别用来存放数据和执行这些数据的指令，而且两个Cache可以同时被CPU访问，减少了争用Cache所造成的冲突，提高了处理器效能。

认识CPU Cache

CPU Cache概述

随着CPU的频率不断提升，而内存的访问速度却没有质的突破，为了弥补访问内存的速度慢，充分发挥CPU的计算资源，提高CPU整体吞吐量，在CPU与内存之间引入了一级Cache。随着热点数据体积越来越大，一级Cache L1已经不满足发展的要求，引入了二级Cache L2，三级Cache L3。（注：若无特别说明，本文的Cache指CPU Cache，高速缓存）CPU Cache在存储器层次结构中的示意如下图：

计算机早已进入多核时代，软件也越来越多的支持多核运行。一个处理器对应一个物理插槽，多处理器间通过QPI总线相连。一个处理器包含多个核，一个处理器间的多核共享L3 Cache。一个核包含寄存器、L1 Cache、L2 Cache，下图是Intel Sandy Bridge CPU架构，一个典型的NUMA多处理器结构：

作为程序员，需要理解计算机存储器层次结构，它对应用程序的性能有巨大的影响。如果需要的程序是在CPU寄存器中的，指令执行时1个周期内就能访问到他们。如果在CPU Cache中，需要130个周期；如果在主存中，需要50200个周期；在磁盘上，大概需要几千万个周期。充分利用它的结构和机制，可以有效的提高程序的性能。

以我们常见的X86芯片为例，Cache的结构下图所示：整个Cache被分为S个组，每个组是又由E行个最小的存储单元——Cache Line所组成，而一个Cache Line中有B（B=64）个字节用来存储数据，即每个Cache Line能存储64个字节的数据，每个Cache Line又额外包含一个有效位(valid bit)、t个标记位(tag bit)，其中valid bit用来表示该缓存行是否有效；tag bit用来协助寻址，唯一标识存储在CacheLine中的块；而Cache Line里的64个字节其实是对应内存地址中的数据拷贝。根据Cache的结构题，我们可以推算出每一级Cache的大小为B×E×S。

那么如何查看自己电脑CPU的Cache信息呢？

什么是CAS

CAS即Compare And Swap的缩写，翻译成中文就是比较并交换，其作用是让CPU比较内存中某个值是否和预期的值相同，如果相同则将这个值更新为新值，不相同则不做更新，也就是CAS是原子性的操作(读和写两者同时具有原子性)，其实现方式是通过借助C/C++调用CPU指令完成的，所以效率很高。
CAS的原理很简单，这里使用一段Java代码来描述

1
2
3
4
5
6
7
8
9

public boolean compareAndSwap(int value, int expect, int update) {
//        如果内存中的值value和期望值expect一样 则将值更新为新值update
    if (value == expect) {
        value = update;
        return true;
    } else {
        return false;
    }
}

大致过程是将内存中的值、我们的期望值、新值交给CPU进行运算，如果内存中的值和我们的期望值相同则将值更新为新值，否则不做任何操作。这个过程是在CPU中完成的，这里不好描述CPU的工作过程，就拿Java代码来描述了。

Unsafe源码分析

Java是在Unsafe(sun.misc.Unsafe)类实现CAS的操作，而我们知道Java是无法直接访问操作系统底层的API的(原因是Java的跨平台性限制了Java不能和操作系统耦合)，所以Java并没有在Unsafe类直接实现CAS的操作，而是通过**JDI(Java Native Interface)**本地调用C/C++语言来实现CAS操作的。
Unsafe有很多个CAS操作的相关方法，这里举例几个

1
2
3
4
5

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

我们拿public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);进行分析，这个方法是比较内存中的一个值(整型)和我们的期望值(var4)是否一样，如果一样则将内存中的这个值更新为var5，参数中的var1是值所在的对象，var2是值在对象(var1)中的内存偏移量，参数var1和参数var2是为了定位出值所在内存的地址。

Unsafe.java在这里发挥的作用有：

1. 将对象引用、值在对象中的偏移量、期望的值和欲更新的新值传递给Unsafe.cpp
2. 如果值更新成功则返回true给开发者，没有更新则返回false

Unsafe.cpp在这里发挥的作用有：

ArrayList循环遍历并删除元素的常见陷阱

在工作和学习中，经常碰到删除ArrayList里面的某个元素，看似一个很简单的问题，却很容易出bug。不妨把这个问题当做一道面试题目，我想一定能难道不少的人。今天就给大家说一下在ArrayList循环遍历并删除元素的问题。首先请看下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.ArrayList;
public class ArrayListRemove
{
　　public static void main(String[]args)
　　{
　　　　ArrayList<String>list=newArrayList<String>();
　　　　list.add("a");
　　　　list.add("b");
　　　　list.add("b");
　　　　list.add("c");
　　　　list.add("c");
　　　　list.add("c");
　　　　remove(list);
　　　　for(Strings:list)
　　　　{
　　　　　　System.out.println("element : "+s);
　　　　}
　　}
　　public static void remove(ArrayList<String> list)
　　{
　　// TODO:
　　}
}

如果要想删除list的b字符，有下面两种常见的错误例子：

错误写法实例一：

1
2
3
4
5
6
7
8
9
10
11

public static void remove(ArrayList<String> list)
{
    for(inti=0;i<list.size();i++)
    {
        Strings=list.get(i);
        if(s.equals("b"))
        {
            list.remove(s);
        }
    }
}

错误的原因：这种最普通的循环写法执行后会发现第二个“b”的字符串没有删掉。

错误写法实例二：

1
2
3
4
5
6
7
8
9
10

public static void remove(ArrayList<String> list)
{
    for(Strings:list)
    {
        if(s.equals("b"))
        {
            list.remove(s);
        }
    }
}

错误的原因：这种for-each写法会报出著名的并发修改异常：java.util.ConcurrentModificationException。

背景

​ 从你刚刚毕业开始最怕的问题就是乱码问题对不对？起码我是。后面渐渐的知道是编码问题，而后面为了出现这种问题就都选择UTF-8，然后后面渐渐的就开始淡忘了这个问题。然后当小弟弟小妹妹问我们这相关的问题的时候，也都是跟他们说，全部改成UTF-8就好了。

​ 但这是一种逃避，其实编码问题困扰我好多年，其实说句实话，真的没有搞懂。之前还有同事在一起相互考问 一个中文到底占用几个字节？ 对不对，你遇到过吗？你回答的上来吗？哈哈

推荐几个常用的地址：

• ASCII：http://tool.oschina.net/commons?type=4

• GB2312简体中文编码表：http://tools.jb51.net/table/gb2312

• Unicode编码：http://tool.chinaz.com/Tools/Unicode.aspx

常见的编码

ASCII

​ 它是现今最早最通用的单字节编码系统,并等同于国际标准ISO/IEC 646，其中一个英文字母（不分大小写）占一个字节的空间。

引申：字节是指一小组相邻的二进制数码。通常是8位作为一个字节，如00001111，换算为十进制。

最小值：-128

作者：薛8

来源：https://juejin.im/post/5c890b4a51882501351d5929

AQS简介

AbstractQueuedSynchronizer抽象队列同步器，简称为AQS，可用于构建阻塞锁或者其他相关同步器的基础框，是Java并发包的基础工具类。通过AQS这个框架可以对同步状态原子性管理、线程的阻塞和解除阻塞、队列的管理进行统一管理。
AQS是抽象类，并不能直接实例化，当需要使用AQS的时候需要继承AQS抽象类并且重写指定的方法，这些重写方法包括线程获取资源和释放资源的方式(如ReentractLock通过分别重写线程获取和释放资源的方式实现了公平锁和非公平锁)，同时子类还需要负责共享变量state的维护，如当state为0时表示该锁没有被占，大于0时候代表该锁被一个或多个线程占领(重入锁)，而队列的维护(获取资源失败入队、线程唤醒、线程的状态等)不需要我们考虑，AQS已经帮我们实现好了。AQS的这种设计模式采用的正是模板方法模式。
总结起来子类的任务有：

1. 通过CAS操作维护共享变量state。
2. 重写资源的获取方式。
3. 重写资源释放的方式。

如果对CAS和Java内存模型还不清楚的，建议先了解这两者之后再食用本文，效果更佳！CAS原理分析及ABA问题详解 什么是Java内存模型？

完成以上三个任务即可实现自己的锁。
AQS作为J.U.C的工具类，面向的是需要实现锁的实现者，而锁面向的是锁的使用者，这两者的区别还是需要搞清楚的。

AQS数据结构

先看AQS有哪些重要的成员变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 头结点，你直接把它当做 当前持有锁的线程 可能是最好理解的
private transient volatile Node head;

// 阻塞的尾节点，每个新的节点进来，都插入到最后，也就形成了一个链表
private transient volatile Node tail;

// 这个是最重要的，不过也是最简单的，代表当前锁的状态，0代表没有被占用，大于0代表有线程持有当前锁
// 之所以说大于0，而不是等于1，是因为锁可以重入嘛，每次重入都加上1
private volatile int state;

// 代表当前持有独占锁的线程，举个最重要的使用例子，因为锁可以重入
// reentrantLock.lock()可以嵌套调用多次，所以每次用这个来判断当前线程是否已经拥有了锁
// if (currentThread == getExclusiveOwnerThread()) {state++}
private transient Thread exclusiveOwnerThread; //继承自AbstractOwnableSynchronizer

基本概念

1、什么是序列化和反序列化

（1）Java序列化是指把Java对象转换为字节序列的过程，而Java反序列化是指把字节序列恢复为Java对象的过程；

（2）序列化：对象序列化的最主要的用处就是在传递和保存对象的时候，保证对象的完整性和可传递性。序列化是把对象转换成有序字节流，以便在网络上传输或者保存在本地文件中。序列化后的字节流保存了Java对象的状态以及相关的描述信息。序列化机制的核心作用就是对象状态的保存与重建。

（3）反序列化：客户端从文件中或网络上获得序列化后的对象字节流后，根据字节流中所保存的对象状态及描述信息，通过反序列化重建对象。

（4）本质上讲，序列化就是把实体对象状态按照一定的格式写入到有序字节流，反序列化就是从有序字节流重建对象，恢复对象状态。

2、为什么需要序列化与反序列化

我们知道，当两个进程进行远程通信时，可以相互发送各种类型的数据，包括文本、图片、音频、视频等， 而这些数据都会以二进制序列的形式在网络上传送。

那么当两个Java进程进行通信时，能否实现进程间的对象传送呢？答案是可以的！如何做到呢？这就需要Java序列化与反序列化了！

换句话说，一方面，发送方需要把这个Java对象转换为字节序列，然后在网络上传送；另一方面，接收方需要从字节序列中恢复出Java对象。