浅谈Java集合框架-来看看LinkedHashMap是啥!

跳槽后,就没怎么看jdk,趁着十一看回点集合框架。我们知道HashMap是无序的,jdk也给我们提供了算是有序的HashMap,即LinkedHashMap。然而它只保留了操作的相对有序,而非TreeMap的Key自然有序。


LinkedHashMap显然继承了HashMap的绝大部分特性,新Entry则添加了beforeafter两个指针,以及维护Entry链表的方法。需要说明的是,HashMap.Entry的单链表无关,那只是用于解决hash冲突而已。

阅读全文

Linux-awk编程

awk是个刁到不行的文本处理命令,查看生产环境日志时,简直就是神操!
新增:awk的数组


  • awk命令

阅读全文

浅谈Java集合框架-比较HashMap与Hashtable

Hashtable实际上就是一个线程安全的HashMap,不过它是个遗留下来的过气类,其性能也并比不少ConcurrentHashMap。


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
//HashMap默认长度是1<<4 aka 16
public Hashtable() {
this(11, 0.75f);
}
//很明显,HashMap没有synchronized,并不线程安全。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
//HashMap的key允许一个null
//HashMap源码:return putForNullKey(value);
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}

modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}

public synchronized V get(Object key) {
//if (key == null)
// return getForNullKey();HashMap的key有null值
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}

阅读全文

浅谈Java集合框架-瞧瞧LinkedArray源码,查询效率为何如此低下?

平时用惯ArrayList插入查询,无视性能而忽略了LinkedArray,今日也反省反省,研究了一下
LinkedArray和ArrayList源码。其实理解两者原理和区别并不难,都是简单数据结构的应用。


LinkedArray源码

双链表的好处就是有前后指针,插入只需要更新指针指向,随机查询则需要遍历。

阅读全文

浅谈Java集合框架-看看HashMap源码,了解它是咋运作的?

初探HashMap源码,显然要理解它的运作并不难,只要基本掌握哈希桶这种数据结构。本文只在源码上对get(K key)put(K key, V value)进行解读,并了解HashMap的原理。我看的是jdk1.7的源码!


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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
threshold = initialCapacity;

//在HashMap类中无用
init();
}

//初始化哈希槽
private void inflateTable(int toSize) {
//threshold只是作为标准值,下面求一个略大于标准值的容量
int capacity = roundUpToPowerOf2(toSize);
//负载因子折算threshold
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//注意Entry本身是链表结构(即桶),table只是桶的列表
table = new Entry[capacity];
//初始化hashseed
initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
//number-1两倍,取最高位1的值
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
//
inflateTable(threshold);
}
//key为null时,hash为0,即table[0]
if (key == null)
//该方法的代码段与下面一致,i=0
return putForNullKey(value);
int hash = hash(key);
//计算下标
int i = indexFor(hash, table.length);
//获取对于hash的桶,e!=null则下一个entry
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//比对key值,若key存在则体会value,并返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
//貌似毫无用处
e.recordAccess(this);
return oldValue;
}
}

modCount++;
//key值不存在则插入
addEntry(hash, key, value, i);
return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
//entry数满标准值,且该槽点不为null。为什么这样判断?因为大于threshold,不代表bucket已经用完,size只是entry的数量
if ((size >= threshold) && (null != table[bucketIndex])) {
//重设标准值,扩容
resize(2 * table.length);
//重新计算hash
hash = (null != key) ? hash(key) : 0;
//重新计算下表
bucketIndex = indexFor(hash, table.length);
}

createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//把新entry插入链表头
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
if (size == 0) {
return null;
}
//前面说过key为null时,hash为0
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}

final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}

int hash = (key == null) ? 0 : hash(key);
//获取hash对应的bucket,遍历Entry
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

void resize(int newCapacity) {

Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

阅读全文

设计模式-状态模式

现实生活中,操作某一固定事物,可能会触发不同状态,例如电灯的开关。代码中也用相类似的情况,调用某对象的同一方法或多个方法,会触发对象内部的某个状态,而这个状态会影响你下一步可能调用的方法。我们这一次就讲讲状态模式。


  • 举例

阅读全文

设计模式-策略模式

前面聊过模版方法,在一个算法中某步骤有多套实现时,可以很有效替换算法步骤。那如果在一套代码中有多种策略呢?更换策略是否还要更改原有的代码?这次说说策略模式。


  • 举例

阅读全文

设计模式-职责链模式

我们总有请假的时候,每个单位可能制度都不一样,但都对请假时间长短有规定不同流程。例如0.5-1天假向经理报告,2-3天假向hr报告,3以上的假期需总经理或老板签字等等。既然有这种状况,程序也务必会遇到此类情况,要说的就是处理此类问题时可能用到的设计模式——职责链模式。


    阅读全文

    设计模式-观察者模式

    业务总会有环环相扣的联动,一环变化会引发后续环的变动。一个对象的变化,可能会引发一个或多个对象的变化,今天我就要说的能引用此种场景的设计模式——观察者模式。


    • 举例

    阅读全文

    SpringMVC拦截器Interceptor

    SpringMVC拦截器是个非常好用的东西,对于每个请求有分别对进入控制器前、执行控制器后渲染之前、渲染之后的行为都能拦截。通常我们用拦截器实现了权限管理、MyBatis分页功能等。


    • 实现HandlerInterceptor接口

    阅读全文