现在项目基本都采用git来进行版本控制，最近比较好奇git的存储机制到底是怎么样的，研究了一下

简单介绍git最重要的算法（SHA-1）

• 通过git log查看，会发现都会有一个40个字符组成的字符串,这个字符串是通过SHA-1算法计算出来的字符串
• SHA-1算法：两个不同的内容进行计算出来的值（消息摘要）理论上来说是不重复的（基于目前来说）

git的存储机制详解

• 先介绍下git的一个命令：git cat-file，查看消息摘要的详细内容；用的时候经常会带上 -p 参数

• 研究过程(基于我本地的一个版本库)

  • 先通过 git log 找到一个commitId，通过 git cat-file 查看 git cat-file -p 71d8f2a8aecfc84b2a72814f525c76c128face53

    1 2 3 4

    tree b346468f50d856cc0a6089e4fe260b4f72c914e5 parent 5987828df851c3d93775e8a1eb49b8d709fd1fb5 author xx <xxx> 1489540261 +0800 committer xxx <xxx> 1489540267 +0800

  • 从这里看出来一个 commit 指向一个 tree （一个tree管理一些tree和一些blob），接下来继续看这个tree到底是什么

  • 继续 git cat-file ：git cat-file -p b346468f50d856cc0a6089e4fe260b4f72c914e5

    1 2 3 4 5 6

    100644 blob e1b5186c600616e89692c94f64f4ed2e525fab23 .gitignore 100644 blob 2572cca5762d11828c4a296bcca7ded879f4929a LICENSE 100644 blob 7ba68141ca2199ab83d3160f700d0e4343298468 README.md 100644 blob ac8522fb58c89951af0089cb090a56f9856c05b0 a.txt 100644 blob 9b285c5c555323213ce7865e536d09e597268706 pom.xml 040000 tree 5165230a25966bca6377f32f80750b0640a9de02 src

  • 上边的结果有blob和tree：这个时候blob通常是一个文件，tree是一个目录

    • 那先来看看blob类型：git cat-file -p e1b5186c600616e89692c94f64f4ed2e525fab23，这个时候看到的是一个文件的内容：

      1 2 3 4

      *.class target/ java-common-utils.iml .idea/

      为什么是这样的呢，因为git通过e1b5186c600616e89692c94f64f4ed2e525fab23指向了.gitignore文件，而这个文件的内容被压缩成另一个文件，这些文件保存在项目的.git目录下的objects目录下，git的cat-file命令将blob还原成原有的文件内容了。网上有压缩的算法

    • 再来看看tree类型：git cat-file -p 5165230a25966bca6377f32f80750b0640a9de02

      1 2	040000 tree 857c7710f03f0b9d33d3110273f525416ee310a6 main 040000 tree b63ccc7fa9ced1d7b84fd5de194a85fe66016bec test

      可以看到还是两个tree，可以一直cat-file下去知道没有tree

  总结

  • git对文件的比对是通过文件内容的SHA-1消息摘要进行对比是否有更改，所以速度会非常快；

越来越多的开发都用MAC，记录实用的操作技巧

• 在terminal的某个文件夹下，需要打开Finder，请输入open .，Finder就打开了，是不是很方便了

web相关

• 干掉状态：从session到token

java Arrays.asList

Arrays.asList相信搞java的基本都用过，但有些坑不一定踩过

坑一

• Arrays.asList返回的List不能进行add和remove操作，为什么呢，来看看源码就明白了

  1 2 3 4 5

  @SafeVarargs @SuppressWarnings("varargs") public static <T> List<T> asList(T... a) { return new ArrayList<>(a); }

在这里看，似乎没什么问题，返回一个ArrayList，那怎么就不能进行add和remove操作了呢,且看下面代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable {
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;
    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }
    @Override
    public int size() {
        return a.length;
    }
    @Override
    public Object[] toArray() {
        return a.clone();
    }
    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)
            return Arrays.copyOf(this.a, size,
                                 (Class<? extends T[]>) a.getClass());
        System.arraycopy(this.a, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
    @Override
    public E get(int index) {
        return a[index];
    }
    @Override
    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }
    @Override
    public int indexOf(Object o) {
        E[] a = this.a;
        if (o == null) {
            for (int i = 0; i < a.length; i++)
                if (a[i] == null)
                    return i;
        } else {
            for (int i = 0; i < a.length; i++)
                if (o.equals(a[i]))
                    return i;
        }
        return -1;
    }
    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(a, Spliterator.ORDERED);
    }
    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        for (E e : a) {
            action.accept(e);
        }
    }
    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        E[] a = this.a;
        for (int i = 0; i < a.length; i++) {
            a[i] = operator.apply(a[i]);
        }
    }
    @Override
    public void sort(Comparator<? super E> c) {
        Arrays.sort(a, c);
    }
}

原来Arrays.asList调用以后生成的ArrayList其实是Arrays的内部类对象，这个类继承了AbstractList，这个List的抽象类对get和remove方法都是需要子类自己实现的，来看看AbstractList的add和remove方法的代码

1
2
3
4
5
6
7
8
9
10

public E remove(int index) {
    throw new UnsupportedOperationException();
}
public void add(int index, E element) {
    throw new UnsupportedOperationException();
}
public boolean add(E e) {
    add(size(), e);
    return true;
}

看到这里就明白了；具体这个ArrayList能做哪些操作，看看他提供出来的API就行了

坑二

• Arrays.asList传入参数是基本类型的话，会把数组当做一个元素，看debug结果：
  

很多时候需要用到vim，特别是查日志，学习一些常用的vim技巧还是很有必要的

命令模式

• h/j/k/l：分别表示向左/向下/向上/向右移动光标
• shift+g：到最后
• ctrl+f：向前一页
• ctrl+b：向后一页
• ctrl+d：向前半页
• ctrl+u：向后半页
• ctrl+e：向上滚动
• ctrl+y：向下滚动
• x：删除当前光标所在的字符
• dd：删除一行
• J：删除当前行的换行符，两行合并一行
• u：撤销上一次操作
• ctrl+r：重做
• a：追加输入
• o：在当前行后另起一行输入
• ZZ：保存并退出
• q!：放弃编辑并退出
• G：跳转到最后一行
• gg：跳转到第一行
• e!：放弃所有修改重新编辑
• help {subject}：帮助文档
• w：向后移动一个单词
• 3w：向后移动三个单词
• b：向前移动一个单词
• 3b：向前移动三个单词
• e：光标移动到下一个单词的最后一个字符
• 3e：光标移动到后三个单词的最后一个字符
• ge：光标移动到上一个单词的最后一个字符
• 3ge：光标移动到前三个单词的最后一个字
• $：移动到行尾
• 0/^：移动到行首
• [n]fh：移动到h的单词上
• [n]Fh：反向搜索
• %：匹配括号
• [n]G：定位到到n行
• [n]%：定位到百分之n行
• H,M,L：分别跳转到当前屏幕的第一行，中间行，最后一行
• ctrl+g：显示当前光标所在位置
• set number：显示行号
• set nonumber：不显示行号
• set ruler：一直显示光标位置
• zz：把当前行放到屏幕正中央
• zt：把当前行放到屏幕顶端
• zb：把当前行放到屏幕底端
• /string：查找；按n可以往下查找,N反向查找，和?string效果相同,支持正则表达式
• set ignorecase/noignorecase：设置是否忽略大小写
• :或/加上下箭头，可以翻看历史查询
• /word>：查找单词word，不会查到类似words的词,但会匹配aword这类词
• /\：只匹配word单词
• set hlsearch：搜索高亮处理
• hlsearch：暂时关闭高亮，下次搜索还会按照原来设置的
• set nowrapscan/wrapscan：设置搜索到头时要不要重新搜索
• [n]G/gg：跳转到n行

越来越多的开发都用mac

• autojump：文件夹跳转神器

  • 安装：brew install autojump
  • 安装完成后添加到shell中：echo ' [[ -s $(brew --prefix)/etc/profile.d/autojump.sh ]] && . $(brew --prefix)/etc/profile.d/autojump.sh' >> ~/.bashrc && source ~/.bashrc
  • 然后就去浪吧：j foldername

• 应用程序在多屏幕及dashboard切换的’战斧’（ShortCat）

  • 快捷键切花应用程序所在dashboard，神器神器
  • 下载地址

• CheatSheet,一键查看各个软件的快捷键

  • 直接长按command键，自己看效果吧
  • 下载地址

• LICEcap，一款简单易用的截屏动图软件

  • 打开玩玩就会了，小而美的软件
  • 下载地址

• charles，强大的抓包软件

  • 功能强大，主要用到的功能就是其抓包和url rewrite功能，不过是收费软件，破解还是购买看个人了
  • 下载地址

• atom，强大的文本编辑器

  • 强大的编辑器，支持各种插件扩展，个人感觉比sublime稍微重量级大一些，但插件挺牛，当初安装这款软件是看到有markdown转pdf的插件，方便易用。平时一般的单个文件打开用sublime，打开文件夹就开始用atom；很多插件可以自己去插件时长看看，挑几款需要的装起来
  • 下载地址

正则表达式是一个比较好用的工具，但其比较难编写，特别是对于新手来说，更是觉得难写；
平时对一些常用的正则做个记录也是个不错的选择，需要用的时候直接拿来用;
下边的匹配在java代码中通常会需要\\来对\进行转义，比如\w在java代码中应该需要写成\\w

参考文章

比较常用的语法及demo

元字符

• .:匹配除换行符以外的任意字符
• \w:匹配字母数字下划线
• \s:匹配空白符
• \d:匹配数字
• \b:匹配单词的开始或结束
• ^:匹配字符串的开始
• $:匹配字符串的结束
• \W:匹配非字母数字下划线
• \S:匹配非空白符
• \D:匹配非数字
• \B:匹配非单词开头或结束的位置
• [^x]匹配除了x外的字符
• [^abc]:匹配除了abc外的字符

限定符（数量限定）

• *:匹配0次或更多次
• +:匹配一次或更多次
• ?:匹配0次货一次
• {n}:匹配n次
• {n,}:匹配n次或更多次
• {n,m}:匹配n到m次

其他匹配

• [abc]*:匹配字符为a或b或c
• 或条件:\(0\d{2}\)\d{8}|0\d{2}-?\d{8},可以匹配：(010)92832482或者010-92832482这两种格式的
• ():括号来表示分组,如((010)|(020))+能匹配010010...或020020...或者010020...或者020010...
• 组号:\b(\w+)\b\s+\1\1\b

常用正则

*

• ctrl+a/e：到行首/行尾
• ctrl+f/b：前进/后退
• ctrl+d/h：删除字符（前面or后面）
• ctrl+p：前一条命令
• ctrl+n：下一条命令
• ctrl+r：查看历史命令，类似history
• ctrl+k：从光标删除到行尾
• Ctrl+w：删除从光标位置前到当前所处单词（Word）的开头
• Ctrl+y：粘贴最后一次被删除的单词
• command+t：新增标签
• command+w：关闭当前标签
• command+n：新增窗口
• command+数字 command+箭头：切换tab
• command+f：查找
• command+enter：全屏/缩小
• command+d：分屏（竖屏）
• command+shift+d：分屏（横屏）
• command+option+箭头 command+[/]：切屏
• command+shift+h：查看历史剪贴板itermkey

google的guava提供了很方便的操作，特别是集合操作；
但今天遇到了个神坑，看了源码才搞定，这里通过源码来分享下；

经过

• 项目里的代码将PO List转成DTO List，这个时候是通过Lists的transform方法来做的
• 但是DTO还需要其他属性来丰富，这个时候，通过for循环将其他的一些属性设置到DTO List的对象中去
• 结果，没设置进去
• 开发大杀器（debug）上，断点到forfor(DTO dto : dtoList)循环里，在for循环代码块里发现一个比较奇特的现象，dto的数据变了，但dtoList里的数据没变
• 想想没道理呀，这两货不是同一个引用吗，怎么会出现这种情况呢？
• 然后开始怀疑人生，找了帮手一起看了下，也看不出来，后来，帮手提醒了一句：看看对象的地址是什么
• 这个时候开始发现，debug的时候，每次鼠标放到dtoList上的时候，这个List里边的元素的对象地址一直在变
• 找到原因了就好办了，一步一步debug，最终发现问题出在了Lists.transform上了

源码解析

下边是一个比较简单的demo

1
2
3
4
5
6
7

List<Integer> intList = Lists.newArrayList(1000000, 200000);
List<Integer> intList1 = Lists.transform(intList, new Function<Integer, Integer>() {
    public Integer apply(Integer input) {
        return input + 100000000;
    }
});
intList1.get(0);

代码比较简单，就是对intList加工后返回intList1；
这个时候debug断点打到intList1.get(0);这行，然后用鼠标上浮的方式查看intList1里边的元素的地址
下边是两次鼠标放上去看的内存地址

从截图中可以看出，这个List的真实类型为TransformingRandomAccessList，这个List有什么特殊呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

private static class TransformingRandomAccessList<F, T> extends AbstractList<T>
      implements RandomAccess, Serializable {
    final List<F> fromList;
    final Function<? super F, ? extends T> function;
    TransformingRandomAccessList(List<F> fromList, Function<? super F, ? extends T> function) {
      this.fromList = checkNotNull(fromList);
      this.function = checkNotNull(function);
    }
    @Override
    public void clear() {
      fromList.clear();
    }
    @Override
    public T get(int index) {
      return function.apply(fromList.get(index));
    }
    @Override
    public Iterator<T> iterator() {
      return listIterator();
    }
    @Override
    public ListIterator<T> listIterator(int index) {
      return new TransformedListIterator<F, T>(fromList.listIterator(index)) {
        @Override
        T transform(F from) {
          return function.apply(from);
        }
      };
    }
    @Override
    public boolean isEmpty() {
      return fromList.isEmpty();
    }
    @Override
    public T remove(int index) {
      return function.apply(fromList.remove(index));
    }
    @Override
    public int size() {
      return fromList.size();
    }
    private static final long serialVersionUID = 0;
}

看到源码就明白了，每次get或iterator都会从新调用function.apply方法，而上边的function的apply方法是return input + 100000000;重新new了对象来返回，我在项目的代码里也是重新new了DTO来返回的；
到这里所有的都明白了；

总结

• Lists的transform是挺好用的，但是只适合不对transform后的List的元素做丰富属性的操作；如果非要用，那么在循环List的时候，重新把元素add到新的List中，然后返回新的List，但这种做法太别扭了；transform的方法还是考虑场景慎用吧
• 不知道这是guava故意这么做的还是真的是个坑，个人还没有get到这么做的意图

joda-collection官网说明了是提供jdk和guava之外的collection操作，所以提供了Grid操作；
Grid顾名思义就是网格的意思，也就是有个(x,y)坐标确定一个元素；

如何引入

现在基本都是采用maven构建方式，在需要的项目pom中添加依赖：

1
2
3
4
5

<dependency>
  <groupId>org.joda</groupId>
  <artifactId>joda-collect</artifactId>
  <version>0.7</version>
</dependency>

源码解析

继承关系

• Grid定义为接口，AbstractGrid为实现该接口的抽象类
• DenseGrid，ImmutableGrid（抽象类），SparseGrid均实现了AbstractGrid抽象类
• DenseImmutableGrid，EmptyGrid，SingletonGrid，SparseImmutableGrid实现了Immutable抽象类
• 其中AbstractGrid，DenseImmutableGrid，EmptyGrid，SingletonGrid和SparseImmutableGrid为包访问权限

看代码

ImmutableGrid的copyOf方法

该方法为从grid获取到具有immutable的grid

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

public static <R> ImmutableGrid<R> copyOf(Grid<R> grid) {
    if (grid == null) {
        throw new IllegalArgumentException("Grid must not be null");
    }
    if (grid instanceof ImmutableGrid) {
        return (ImmutableGrid<R>) grid;
    }
    validateCounts(grid.rowCount(), grid.columnCount
    if (grid.size() == 0) {
        return new EmptyGrid<R>(grid.rowCount(), grid.columnCount());
    }
    if (grid.size() == 1) {
        Cell<R> cell = grid.cells().iterator().next();
        return new SingletonGrid<R>(grid.rowCount(), grid.columnCount(), cell);
    }
    if (grid.size() >= (grid.rowCount() * grid.columnCount() / 2)) {
        return DenseImmutableGrid.create(grid);
    }
    return new SparseImmutableGrid<R>(grid);
}

• 如果grid为空的，那么返回EmptyGrid；其实返回这个用处不大，本来就是个immutable的，不能往里插数据
• 如果grid所持有的对象个数为1，那么返回的是SingletonGrid；
• 如果grid所持有的对象个数大于等于grid总大小的一般，就用DenseImmutableGrid（非稀疏的不可变grid），否则返回的是SparseImmutableGrid（稀疏的不可变grid）

关于稀疏（dense）grid和非稀疏(sparse)grid

两者的区别在于存储的方式不同：dense采用的的数组的方式存储信息，而sparse采用SortedSet<Cell<V>>来作为存储结构；下边先介绍Cell是什么玩意

Cell接口是Grid的一个内部接口，MutableCell和ImmutableCell采用相同的存储结构且都实现AbstractCell抽象类，存储结构为row，column，value

接下来看看SparseGrid的实现

1
2
3
4
5
6

private final int rowCount;
private final int columnCount;
private final SortedSet<Cell<V>> cells;
public static <R> SparseGrid<R> create(int rowCount, int columnCount) {
    return new SparseGrid<R>(rowCount, columnCount, new TreeSet<Cell<R>>(AbstractCell.<R>comparator()));
}

首先，通过SortedSet来存储，在creat方法中可以看到，实际采用的是SortedSet的实现类TreeSet来存储；然后存储总行数和总列数；为什么不直接声明为TreeSet来存储呢，主要是为了扩展性考虑，面向接口编程嘛；对于稀疏的采用Set来存储而不是数组，可以节省存储空间

AbstractCell实现了Comparator接口，利用row和column来进行排序；

cell(int row, int column)方法来获取指定的cell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

@Override
public Cell<V> cell(int row, int column) {
    if (exists(row, column)) {
        SortedSet<Cell<V>> tail = cells.tailSet(finder(row, column));
        if (tail.size() > 0) {
            Cell<V> cell = tail.first();
            if (cell.getRow() == row && cell.getColumn() == column) {
                return cell;
            }
        }
    }
    return null;
}
@Override
public boolean exists(int row, int column) {
    return row >= 0 && row < rowCount() && column >= 0 && column < columnCount();
}

通过SortedSet来查询具体的cell；

再来看看DenseGrid

1
2
3
4

private final int rowCount;
private final int columnCount;
private int size;
private final V[] values;

从代码里看出，采用的是数组的存储方式，因为当数据比较稠密的时候，浪费的空间的少量的，这种方式相比较SparseGrid，效率会高，实现比较简单；

1
2
3
4
5
6
7
8
9

public static <V> DenseGrid<V> create(int rowCount, int columnCount) {
    return new DenseGrid<V>(rowCount, columnCount);
}
private DenseGrid(int rowCount, int columnCount) {
    validateCounts(rowCount, columnCount);
    this.rowCount = rowCount;
    this.columnCount = columnCount;
    this.values = (V[]) new Object[rowCount * columnCount];
}

代码里可以看出来，最开始构造方法就已经分配了最大容量的数组；

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

@Override
public V get(int row, int column) {
    if (exists(row, column)) {
        return values[row * columnCount + column];
    }
    return null;
}
@Override
public Cell<V> cell(int row, int column) {
    V value = get(row, column);
    return (value != null ? ImmutableCell.of(row, column, value) : null);
}

从get的代码可以看出来，就是简单的数组下标定位，效率非常高；其他一些需要get的操作都是通过数组下标的方式来做的，例如public List column(int column)和public List row(int row)等方法；

总结下，稀疏Grid和非稀疏Grid最大的区别就是以时间换空间还是以空间换时间的问题；通过不同的存储结构来实现；

总结

• 从Grid的源码分析来看，执行效率还是不错的
• Grid的使用场景还是有一些的，比如一些业务场景中的需要多个map来实现的业务逻辑，可以考虑Grid的实现方式，看看哪种实现方式更方便及效率更高；