Zacard's Notes


  • 首页

  • 分类

  • 归档

  • 标签

  • 关于

  • 搜索
close
Zacard's Notes

红黑树&TreeMap的实现原理

发表于 2016-08-26 | 分类于 软件技术 | | 阅读次数

前言

由于TreeMap的实现原理就是以红黑树为基础数据结构的,所以基本也是红黑树的原理解读。

红黑树

红黑树是一种自平衡的二叉查找树。是一种复杂但高效的数据结构,它可以在O(log n)时间内做查找,插入和删除。

红黑树的规定:

1.一个节点只能是红色或者黑色
2.根节点是黑色
3.每个叶节点(null节点/空节点)为黑色
4.如果一个节点为红色,则他们的2个子节点都为黑色
5.从任意节点到其每个叶节点

红黑树结构java代码示例:(TreeMap中的内部类Entry)

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
/**
* 红黑树节点结构
*/
static final class Entry<K, V> implements Map.Entry<K, V> {
K key; // 红黑树的排序字段
V value; // 节点存储的值
Entry<K, V> left; // 左子树节点
Entry<K, V> right; // 右子树节点
Entry<K, V> parent; // 父节点
boolean color = BLACK; // 节点颜色,默认为黑
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
return valEquals(key, e.getKey()) && valEquals(value, e.getValue());
}
public int hashCode() {
int keyHash = (key == null ? 0 : key.hashCode());
int valueHash = (value == null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
阅读全文 »
Zacard's Notes

chmod777原理

发表于 2016-08-19 | 分类于 软件技术 | | 阅读次数

背景

很多Linux新手发现某个文件没有相关权限,一言不合就是chmod 777。首先说一句,chmod 777应该杜绝使用,尤其生产环境。

那chmod 777的背后原理到底是什么呢?

Unix权限设计

首先Unix系统的权限分为三种,分别为拥有者(owner)、用户组(group)、其他用户(other)。用ll命令可以查看具体的权限设置,如下图所示:

每个项目前面那一串字母和横杠就是权限。第一位指的是文件类型:-代表普通文件,d代表文件夹。后面9位分为三组,每组代表了对应用户的权限:

阅读全文 »
Zacard's Notes

Docker学习系列七:构建jetty镜像

发表于 2016-08-12 | 分类于 软件技术 | | 阅读次数

前言

Docker hub官方已经维护了一套比较完善的jetty镜像,但是依赖的是openjdk。所以这里只是把jdk换成之前学习系列中构建过的oracle-jdk8。

Dockerfile描述

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
FROM oraclejdk8
MAINTAINER zacard <[email protected]>
# add our user and group first to make sure their IDs get assigned consistently, regardless of whatever dependencies get added
RUN addgroup -S jetty && adduser -D -S -H -G jetty jetty && rm -rf /etc/group- /etc/passwd- /etc/shadow-
ENV JETTY_HOME /usr/local/jetty
ENV PATH $JETTY_HOME/bin:$PATH
RUN mkdir -p "$JETTY_HOME"
WORKDIR $JETTY_HOME
ENV JETTY_BASE /var/lib/jetty
RUN mkdir -p "$JETTY_BASE"
ENV JETTY_VERSION 9.3.10.v20160621
ENV JETTY_TGZ_URL https://repo1.maven.org/maven2/org/eclipse/jetty/jetty-distribution/$JETTY_VERSION/jetty-distribution-$JETTY_VERSION.tar.gz
# GPG Keys are personal keys of Jetty committers (see https://dev.eclipse.org/mhonarc/lists/jetty-users/msg05220.html)
ENV JETTY_GPG_KEYS \
# 1024D/8FB67BAC 2006-12-10 Joakim Erdfelt <[email protected]>
B59B67FD7904984367F931800818D9D68FB67BAC \
# 1024D/D7C58886 2010-03-09 Jesse McConnell (signing key) <[email protected]>
5DE533CB43DAF8BC3E372283E7AE839CD7C58886
RUN set -xe \
# Install required packages for build time. Will be removed when build finishes.
&& apk add --no-cache --virtual .build-deps gnupg coreutils curl \
&& curl -SL "$JETTY_TGZ_URL" -o jetty.tar.gz \
&& curl -SL "$JETTY_TGZ_URL.asc" -o jetty.tar.gz.asc \
&& export GNUPGHOME="$(mktemp -d)" \
&& for key in $JETTY_GPG_KEYS; do \
gpg --keyserver ha.pool.sks-keyservers.net --recv-keys "$key"; done \
&& gpg --batch --verify jetty.tar.gz.asc jetty.tar.gz \
&& rm -r "$GNUPGHOME" \
&& tar -xvzf jetty.tar.gz \
&& mv jetty-distribution-$JETTY_VERSION/* ./ \
&& sed -i '/jetty-logging/d' etc/jetty.conf \
&& rm -fr demo-base javadoc \
&& rm jetty.tar.gz* \
&& rm -fr jetty-distribution-$JETTY_VERSION/ \
# Get the list of modules in the default start.ini and build new base with those modules, then add setuid
&& cd $JETTY_BASE \
&& modules="$(grep -- ^--module= "$JETTY_HOME/start.ini" | cut -d= -f2 | paste -d, -s)" \
&& java -jar "$JETTY_HOME/start.jar" --add-to-startd="$modules,setuid" \
# Remove installed packages and various cleanup
&& apk del .build-deps \
&& rm -fr .build-deps \
&& rm -rf /tmp/hsperfdata_root
WORKDIR $JETTY_BASE
ENV TMPDIR /tmp/jetty
RUN set -xe \
&& mkdir -p "$TMPDIR" \
&& chown -R jetty:jetty "$TMPDIR" "$JETTY_BASE"
COPY docker-entrypoint.sh /
EXPOSE 8080
ENTRYPOINT ["/docker-entrypoint.sh"]
CMD ["java","-jar","/usr/local/jetty/start.jar"]
阅读全文 »
Zacard's Notes

java是值传递还是引用传递

发表于 2016-08-09 | 分类于 软件技术 | | 阅读次数

java到底是值传递还是引用传递

“Java manipulates objects ‘by reference,’ but it passes object references to methods ‘by value.’” –David Flanagan

大神解释了:java操作对象都是通过引用传递,而给方法传参都是通过值传递

首先,操作对象通过引用传递这个大家应该没有什么争议。但是方法传参都是通过值传递,估计大家还有些疑虑。

代码验证

我们知道,如果是值传递,那么实际上传的是一份拷贝。引用传递的话一般传递的是内存地址(看具体的jvm实现)。
所以,值传递是无法修改原值的,而引用传递是可以修改原值。

请看以下代码例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@Test
public void testPassedByValueOrReference() {
char[] c1 = {'a','b'};
change1(c1);
System.out.println("c1 after change1:" + Arrays.toString(c1));
change2(c1);
System.out.println("c1 after change2:" + Arrays.toString(c1));
}
private void change1(char[] c1) {
char[] c2 = {'e','f'};
c1 = c2;
}
private void change2(char[] c1) {
char[] c2 = {'e','f'};
c1[0] = c2[0];
}

输出:

c1 after change1:[a, b]

c1 after change2:[e, b]

我们知道,数组是个对象。传递给2个不同的方法,确出现了不一致的行为,既有点像值传递,有好像是引用传递。我们来看看这2个方法在内存中到底做了什么:

阅读全文 »
Zacard's Notes

docker学习系列六:构建zookeeper镜像

发表于 2016-07-15 | 分类于 软件技术 | | 阅读次数

什么是zookeeper

zookeeper 是一个分布式的,开源的协调服务框架,服务于分布式应用程序。

为什么要zookeeper

可以将分布式应用从处理协调服务的泥潭中解救出来。且性能优越,设计简洁优雅。

  • 顺序一致性: 来自客户端的更新操作将会按照顺序被作用
  • 原子性操作: 更新要么全部成功,要么全部失败,没有部分的结果
  • 统一的系统镜像: 无论客户端链接的是哪台服务器,都能获得同样的服务视图,也就是说他是无状态的
  • 可靠性保证: 一旦写入操作被执行(作用到服务器),这个状态将会被持久化,直到其他客户端的修改生效
  • 时间线特性: 客户端访问服务器系统镜像能在一个特定时间访问内保证当前系统是实时更新的

Dockfile

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
FROM oraclejdk8
MAINTAINER zacard <[email protected]>
# Install required packages
RUN apk add --no-cache \
bash \
su-exec
ENV ZOO_USER zookeeper
ENV ZOO_CONF_DIR /conf
ENV ZOO_DATA_DIR /data
ENV ZOO_DATA_LOG_DIR /datalog
# Add a user and make dirs
RUN set -x \
&& adduser -D "$ZOO_USER" \
&& mkdir -p "$ZOO_DATA_LOG_DIR" "$ZOO_DATA_DIR" "$ZOO_CONF_DIR" \
&& chown "$ZOO_USER:$ZOO_USER" "$ZOO_DATA_LOG_DIR" "$ZOO_DATA_DIR" "$ZOO_CONF_DIR"
ARG GPG_KEY=C823E3E5B12AF29C67F81976F5CECB3CB5E9BD2D
ARG DISTRO_NAME=zookeeper-3.4.9
# Download Apache Zookeeper, verify its PGP signature, untar and clean up
RUN set -x \
&& apk add --no-cache --virtual .build-deps \
gnupg \
&& wget -q "http://www.apache.org/dist/zookeeper/$DISTRO_NAME/$DISTRO_NAME.tar.gz" \
&& wget -q "http://www.apache.org/dist/zookeeper/$DISTRO_NAME/$DISTRO_NAME.tar.gz.asc" \
&& export GNUPGHOME="$(mktemp -d)" \
&& gpg --keyserver ha.pool.sks-keyservers.net --recv-key "$GPG_KEY" \
&& gpg --batch --verify "$DISTRO_NAME.tar.gz.asc" "$DISTRO_NAME.tar.gz" \
&& tar -xzf "$DISTRO_NAME.tar.gz" \
&& mv "$DISTRO_NAME/conf/"* "$ZOO_CONF_DIR" \
&& rm -r "$GNUPGHOME" "$DISTRO_NAME.tar.gz" "$DISTRO_NAME.tar.gz.asc" \
&& apk del .build-deps
WORKDIR $DISTRO_NAME
VOLUME ["$ZOO_DATA_DIR", "$ZOO_DATA_LOG_DIR"]
ENV ZOO_PORT 2181
EXPOSE $ZOO_PORT
ENV PATH $PATH:/$DISTRO_NAME/bin
ENV ZOOCFGDIR $ZOO_CONF_DIR
COPY docker-entrypoint.sh /
ENTRYPOINT ["/docker-entrypoint.sh"]
CMD ["zkServer.sh", "start-foreground"]

注意:这里依赖的镜像oraclejdk8请查看之前的文章“Docker学习系列五:构建oracle-jdk8镜像”

阅读全文 »
Zacard's Notes

创造Lambda风格的mybatis批量操作

发表于 2016-05-31 | 分类于 软件技术 | | 阅读次数

mybatis批量操作

mybatis如何批量插入呢?常用的做法如下代码所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// UserDao.java
/**
* 批量插入
*/
int batchInsert(@Param("users") List<User> users);
// UserDao.xml
<insert id="batchInsert">
INSERT INTO user (name,password) VALUES
<foreach collection="users" item="user" index="index" separator=",">
(#{user.name},#{user.password})
</foreach>
</insert>

但是,这样有个影藏的bug:当user集合超过一定数量,会导致动态拼接的sql过长而导致执行报错。并且,批量更新就不能使用这种形式了。

阅读全文 »
Zacard's Notes

ThreadLocal的作用与原理

发表于 2016-05-23 | 分类于 软件技术 | | 阅读次数

背景

spring默认bean的注册形式是单例模式。那spring是如何解决并发安全问题的呢?就是通过ThreadLocal。到底ThreadLocal有和“魔力”能让普通类变成线程安全的类呢?

原理

先来看看ThreadLocal.java的源码注释:

This class provides thread-local variables. These variables differ from their normal counterparts in that each thread that accesses one (via its {@code get} or {@code set} method) has its own, independently initialized copy of the variable. {@code ThreadLocal} instances are typically private static fields in classes that wish to associate state with a thread (e.g.,a user ID or Transaction ID).

大致意思:

这个类提供线程局部变量。这种在多线程环境下访问(通过get或set方法)时,能保证各个线程里的变量相对独立于其他线程内的变量。ThreadLocal实例通常是private static类型的,用于管理线程上下文。

也就是说,Threadlocal提供了作用范围为线程的局部变量,这种变量只在线程生命周期内起作用。减少了线程内多个方法之间公共变量传递的复杂度。

这里关于线程安全的类有一个普遍适用的原则:如果一个类没有实例私有属性,或者实例私有属性也是无状态的类,那么这个类就是无状态的类。而一个无状态的类肯定是线程安全的类。

而用ThreadLocal包装类的所有实例私有属性后,这个类就没有实例私有属性了,那么这个类就是一个无状态类,因此也是一个线程安全的类。这也是spring使用ThreeadLocal处理bean的默认方式。

阅读全文 »
Zacard's Notes

Docker学习系列五:构建oracle-jdk8镜像

发表于 2016-05-17 | 分类于 软件技术 | | 阅读次数

前言

由于docker官方的jdk镜像都是openjdk,与我们实际开发上线的jdk环境不符。因此需要构建一个oracle-jdk8的基础镜像。

参考的是dockerhub中一个oracle-jdk高star的配置:传送门

Dockerfile描述

# AlpineLinux with a glibc-2.21 and Oracle Java 8
FROM alpine:3.3

MAINTAINER zacard <[email protected]>
# Java Version and other ENV
ENV JAVA_VERSION_MAJOR=8 \
    JAVA_VERSION_MINOR=92 \
    JAVA_VERSION_BUILD=14 \
    JAVA_PACKAGE=jdk \
    JAVA_HOME=/opt/jdk \
    PATH=${PATH}:/opt/jdk/bin \
    LANG=C.UTF-8

# do all in one step
RUN apk upgrade --update && \
    apk add --update curl ca-certificates bash && \
    for pkg in glibc-2.23-r1 glibc-bin-2.23-r1 glibc-i18n-2.23-r1; do curl -sSL https://github.com/andyshinn/alpine-pkg-glibc/releases/download/2.23-r1/${pkg}.apk -o /tmp/${pkg}.apk; done && \
    apk add --allow-untrusted /tmp/*.apk && \
    rm -v /tmp/*.apk && \
    ( /usr/glibc-compat/bin/localedef --force --inputfile POSIX --charmap UTF-8 C.UTF-8 || true ) && \
    echo "export LANG=C.UTF-8" > /etc/profile.d/locale.sh && \
    /usr/glibc-compat/sbin/ldconfig /lib /usr/glibc-compat/lib && \
    mkdir /opt && curl -jksSLH "Cookie: oraclelicense=accept-securebackup-cookie" -o /tmp/java.tar.gz \
    http://download.oracle.com/otn-pub/java/jdk/${JAVA_VERSION_MAJOR}u${JAVA_VERSION_MINOR}-b${JAVA_VERSION_BUILD}/${JAVA_PACKAGE}-${JAVA_VERSION_MAJOR}u${JAVA_VERSION_MINOR}-linux-x64.tar.gz && \
    gunzip /tmp/java.tar.gz && \
    tar -C /opt -xf /tmp/java.tar && \
    apk del curl glibc-i18n && \
    ln -s /opt/jdk1.${JAVA_VERSION_MAJOR}.0_${JAVA_VERSION_MINOR} /opt/jdk && \
    rm -rf /opt/jdk/*src.zip \
        /opt/jdk/lib/missioncontrol \
        /opt/jdk/lib/visualvm \
        /opt/jdk/lib/*javafx* \
        /opt/jdk/jre/plugin \
        /opt/jdk/jre/bin/javaws \
        /opt/jdk/jre/bin/jjs \
        /opt/jdk/jre/bin/keytool \
        /opt/jdk/jre/bin/orbd \
        /opt/jdk/jre/bin/pack200 \
        /opt/jdk/jre/bin/policytool \
        /opt/jdk/jre/bin/rmid \
        /opt/jdk/jre/bin/rmiregistry \
        /opt/jdk/jre/bin/servertool \
        /opt/jdk/jre/bin/tnameserv \
        /opt/jdk/jre/bin/unpack200 \
        /opt/jdk/jre/lib/javaws.jar \
        /opt/jdk/jre/lib/deploy* \
        /opt/jdk/jre/lib/desktop \
        /opt/jdk/jre/lib/*javafx* \
        /opt/jdk/jre/lib/*jfx* \
        /opt/jdk/jre/lib/amd64/libdecora_sse.so \
        /opt/jdk/jre/lib/amd64/libprism_*.so \
        /opt/jdk/jre/lib/amd64/libfxplugins.so \
        /opt/jdk/jre/lib/amd64/libglass.so \
        /opt/jdk/jre/lib/amd64/libgstreamer-lite.so \
        /opt/jdk/jre/lib/amd64/libjavafx*.so \
        /opt/jdk/jre/lib/amd64/libjfx*.so \
        /opt/jdk/jre/lib/ext/jfxrt.jar \
        /opt/jdk/jre/lib/ext/nashorn.jar \
        /opt/jdk/jre/lib/oblique-fonts \
        /opt/jdk/jre/lib/plugin.jar \
        /tmp/* /var/cache/apk/* && \
    echo 'hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4' >> /etc/nsswitch.conf

# EOF

说明

为什么要基于alpine:3.3

看考官方java镜像中有关java:alpine的说明:传送门

摘录其中一段:

This variant is highly recommended when final image size being as small as possible is desired

官方推荐使用基于alpine制作的镜像。

build镜像

docker build -t oraclejdk8 .

p.s:由于此镜像需要下载一些基础包和jdk,可能需要比较长的build时间,同时可能需要翻墙~

测试镜像

docker run -ti --rm oraclejdk8 java -version

保存镜像

docker save -o jdk8.tar oraclejdk8

加载镜像

docker load -i jdk8.tar
Zacard's Notes

Docker学习系列四:Docker Compose

发表于 2016-05-13 | 分类于 软件技术 | | 阅读次数

什么是Docker Compose

Docker Compose是一个用来定义和运行docker应用服务(一个或者多个dacker容器应用)的工具。使用Compose file来配置管理docker应用服务。

为什么要用Docker Compose

先来看下一下例子:

docker run --name jetty -p 8881:8080 -p 22 -d jetty;
docker run --name jenkins -p 8882:8080 --link -d jetty:jetty jenkins;

这段运行的命令是要先运行一个jetty容器,然后启用一个jenkins容器,同时链接到之前启动的jetty容器。命令显的冗长且极容易敲错或者漏敲。而且不容易记忆,迁移复杂。

如果使用Docker Compose的形式,只需配置一个docker-compose.yml文件即可。如下所示:

services:
  jetty:
      images:jetty
    container_name:jetty
      ports:
        - "8881:8080"
        - "22"
  jenkins:
    imagesLjenkins
    container_name:jenkins
    ports:
      - "8882:8080"
    links:
      jetty

然后运行命令:

docker-compose up -d

即可做到和之前的命令一样的效果。

如同Dockerfile之于镜像构建,Compose file使从Docker image运行Docker contain的过程结构化、透明化。并使之保留运行的记录。

阅读全文 »
Zacard's Notes

Docker学习系列三:Registry

发表于 2016-05-13 | 分类于 软件技术 | | 阅读次数

什么是registry

Docker Registry是一个docker仓库,用来存储和分享docker镜像。类似于Github。

为什么需要docker registry

这里应该说为什么需要配置一个私有的docker registry。我们知道,已经有dockerhub了,而且官方也提供私有仓库的功能。

因为访问官方的dockerhub,是要良好的网络。而且当我们部署发布的时候,肯定不希望dockeruhb在维护或者故障。而我们配置私有的docker registry可以很好的避免此类问题。

部署私有的docker registry

pull官方的registry

docker pull registry:2.4

运行registry

命令:

docker run -d -p 5000:5000 --restart=always --name registry -v /data/registry:/var/lib/registry registry:2.4

使用Compose file编排(创建docker-compose.yml):

registry:
  restart: always
  image: registry:2.4
  container_name: registry
  ports:
    - 5000:5000
  volumes:
    - /data/registry:/var/lib/registry

然后使用命令:

docker-compose up -d
阅读全文 »
1…345…7
zacard

zacard

优生笑,菜鸟哭

65 日志
2 分类
105 标签
RSS
GitHub Weibo ZhiHu
Links
  • DingDang's Notes
© 2015 - 2021 zacard
由 Hexo 强力驱动
主题 - NexT.Mist