邱永臣叫西门追雪

喜剧演员,兼开发工程师(github.com/qiuyongchen)


  • Home

  • Archives

  • Search

c3p0的连接池优化导致的异常

Posted on 2016-05-29
Symbols count in article: 10k | Reading time ≈ 17 mins.

在项目“物业报修系统”里,框架是SpringMVC/Spring/MyBatis,而MyBatis在底层调用的是c3p0,我在试图优化c3p0时犯了一些错误,访问数据库时有时会超时,有时不会,超时会抛出以下异常:

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
org.mybatis.spring.MyBatisSystemException: nested exception is org.apache.ibatis.exceptions.PersistenceException:
### Error querying database. Cause: org.springframework.jdbc.CannotGetJdbcConnectionException: Could not get JDBC Connection; nested exception is java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.
### The error may exist in file [C:\Users\DELL\Documents\propertyManagement\target\classes\mapper\AdminDao.xml]
### The error may involve com.ilovecl.dao.AdminDao.queryById
### The error occurred while executing a query
### Cause: org.springframework.jdbc.CannotGetJdbcConnectionException: Could not get JDBC Connection; nested exception is java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.

at org.mybatis.spring.MyBatisExceptionTranslator.translateExceptionIfPossible(MyBatisExceptionTranslator.java:76)
at org.mybatis.spring.SqlSessionTemplate$SqlSessionInterceptor.invoke(SqlSessionTemplate.java:399)
at com.sun.proxy.$Proxy13.selectOne(Unknown Source)
at org.mybatis.spring.SqlSessionTemplate.selectOne(SqlSessionTemplate.java:165)
at org.apache.ibatis.binding.MapperMethod.execute(MapperMethod.java:69)
at org.apache.ibatis.binding.MapperProxy.invoke(MapperProxy.java:53)
at com.sun.proxy.$Proxy14.queryById(Unknown Source)
at com.ilovecl.dao.AdminDaoTest.queryById(AdminDaoTest.java:30)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:483)
at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
at org.springframework.test.context.junit4.statements.RunBeforeTestMethodCallbacks.evaluate(RunBeforeTestMethodCallbacks.java:73)
at org.springframework.test.context.junit4.statements.RunAfterTestMethodCallbacks.evaluate(RunAfterTestMethodCallbacks.java:82)
at org.springframework.test.context.junit4.statements.SpringRepeat.evaluate(SpringRepeat.java:73)
at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:271)
at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.runChild(SpringJUnit4ClassRunner.java:224)
at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.runChild(SpringJUnit4ClassRunner.java:83)
at org.junit.runners.ParentRunner$3.run(ParentRunner.java:238)
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:63)
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:236)
at org.junit.runners.ParentRunner.access$000(ParentRunner.java:53)
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:229)
at org.springframework.test.context.junit4.statements.RunBeforeTestClassCallbacks.evaluate(RunBeforeTestClassCallbacks.java:61)
at org.springframework.test.context.junit4.statements.RunAfterTestClassCallbacks.evaluate(RunAfterTestClassCallbacks.java:68)
at org.junit.runners.ParentRunner.run(ParentRunner.java:309)
at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.run(SpringJUnit4ClassRunner.java:163)
at org.junit.runner.JUnitCore.run(JUnitCore.java:160)
at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:119)
at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:42)
at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:234)
at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:74)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:483)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)
Caused by: org.apache.ibatis.exceptions.PersistenceException:
### Error querying database. Cause: org.springframework.jdbc.CannotGetJdbcConnectionException: Could not get JDBC Connection; nested exception is java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.
### The error may exist in file [C:\Users\DELL\Documents\propertyManagement\target\classes\mapper\AdminDao.xml]
### The error may involve com.ilovecl.dao.AdminDao.queryById
### The error occurred while executing a query
### Cause: org.springframework.jdbc.CannotGetJdbcConnectionException: Could not get JDBC Connection; nested exception is java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.
at org.apache.ibatis.exceptions.ExceptionFactory.wrapException(ExceptionFactory.java:30)
at org.apache.ibatis.session.defaults.DefaultSqlSession.selectList(DefaultSqlSession.java:122)
at org.apache.ibatis.session.defaults.DefaultSqlSession.selectList(DefaultSqlSession.java:113)
at org.apache.ibatis.session.defaults.DefaultSqlSession.selectOne(DefaultSqlSession.java:73)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:483)
at org.mybatis.spring.SqlSessionTemplate$SqlSessionInterceptor.invoke(SqlSessionTemplate.java:386)
... 39 more
Caused by: org.springframework.jdbc.CannotGetJdbcConnectionException: Could not get JDBC Connection; nested exception is java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.
at org.springframework.jdbc.datasource.DataSourceUtils.getConnection(DataSourceUtils.java:80)
at org.mybatis.spring.transaction.SpringManagedTransaction.openConnection(SpringManagedTransaction.java:82)
at org.mybatis.spring.transaction.SpringManagedTransaction.getConnection(SpringManagedTransaction.java:68)
at org.apache.ibatis.executor.BaseExecutor.getConnection(BaseExecutor.java:315)
at org.apache.ibatis.executor.SimpleExecutor.prepareStatement(SimpleExecutor.java:75)
at org.apache.ibatis.executor.SimpleExecutor.doQuery(SimpleExecutor.java:61)
at org.apache.ibatis.executor.BaseExecutor.queryFromDatabase(BaseExecutor.java:303)
at org.apache.ibatis.executor.BaseExecutor.query(BaseExecutor.java:154)
at org.apache.ibatis.executor.CachingExecutor.query(CachingExecutor.java:102)
at org.apache.ibatis.executor.CachingExecutor.query(CachingExecutor.java:82)
at org.apache.ibatis.session.defaults.DefaultSqlSession.selectList(DefaultSqlSession.java:120)
... 46 more
Caused by: java.sql.SQLException: An attempt by a client to checkout a Connection has timed out.
at com.mchange.v2.sql.SqlUtils.toSQLException(SqlUtils.java:106)
at com.mchange.v2.sql.SqlUtils.toSQLException(SqlUtils.java:65)
at com.mchange.v2.c3p0.impl.C3P0PooledConnectionPool.checkoutPooledConnection(C3P0PooledConnectionPool.java:527)
at com.mchange.v2.c3p0.impl.AbstractPoolBackedDataSource.getConnection(AbstractPoolBackedDataSource.java:128)
at org.springframework.jdbc.datasource.DataSourceUtils.doGetConnection(DataSourceUtils.java:111)
at org.springframework.jdbc.datasource.DataSourceUtils.getConnection(DataSourceUtils.java:77)
... 56 more
Caused by: com.mchange.v2.resourcepool.TimeoutException: A client timed out while waiting to acquire a resource from com.mchange.v2.resourcepool.BasicResourcePool@290222c1 -- timeout at awaitAvailable()
at com.mchange.v2.resourcepool.BasicResourcePool.awaitAvailable(BasicResourcePool.java:1317)
at com.mchange.v2.resourcepool.BasicResourcePool.prelimCheckoutResource(BasicResourcePool.java:557)
at com.mchange.v2.resourcepool.BasicResourcePool.checkoutResource(BasicResourcePool.java:477)
at com.mchange.v2.c3p0.impl.C3P0PooledConnectionPool.checkoutPooledConnection(C3P0PooledConnectionPool.java:525)
... 59 more

我先是检查代码逻辑,没发现哪个地方会出错,再看Spring配置里关于c3p0的部分:

1
2
3
4
5
6
7
8
<!--c3p0连接池的私有属性-->
<property name="maxPoolSize" value="4000"/>
<property name="minPoolSize" value="1"/>
<property name="autoCommitOnClose" value="false"/>
<!--获取连接超时时间-->
<property name="checkoutTimeout" value="1024"/>
<!--获取失败的重试次数-->
<property name="acquireRetryAttempts" value="30"/>

咋一眼看过去,找不到错误,我这时想起我的数据库放在阿里云上,我想:“会不会是运行数据库的机器配置不好,没法及时响应我请求?”。于是我加了一条initialPoolSize优化选项,在建立与数据库的连接时,试图建100个(我想,建立这么多连接,怎么地也会成功一个吧),配置如下:

1
2
3
4
5
6
7
8
9
10
11
<!--试图进行的优化-->
<property name="initialPoolSize" value="100"/>

<!--c3p0连接池的私有属性-->
<property name="maxPoolSize" value="4000"/>
<property name="minPoolSize" value="1"/>
<property name="autoCommitOnClose" value="false"/>
<!--获取连接超时时间-->
<property name="checkoutTimeout" value="1024"/>
<!--获取失败的重试次数-->
<property name="acquireRetryAttempts" value="30"/>

优化之后,虽然效果好了一些,但偶尔依旧会有超时的情况,于是我再仔细研究代码和配置,直到我发现了上面那些配置里有一条:

1
<property name="checkoutTimeout" value="1024"/>

将获取连接的超时时间设置为1024毫秒,在1秒多一点的时间里如果没获取到连接就返回失败并抛出异常。

此时,我突然反应过来:远程机器那么渣,在10秒内能和远在千里之外的它建立连接我就该嗨皮了,居然还要求1秒就建立成功,失败是正常的,能成功都是运气。

于是我将它注释掉,也注释掉之前加上去的initialPoolSize优化,如下:

1
2
3
4
5
6
7
8
9
<!--<property name="initialPoolSize" value="100"/>-->
<!--c3p0连接池的私有属性-->
<property name="maxPoolSize" value="4000"/>
<property name="minPoolSize" value="1"/>
<property name="autoCommitOnClose" value="false"/>
<!--获取连接超时时间-->
<!--<property name="checkoutTimeout" value="1024"/>-->
<!--获取失败的重试次数-->
<property name="acquireRetryAttempts" value="30"/>

如此,再也不会超时了。

JUnit4整合Spring出现的包不兼容问题

Posted on 2016-05-29
Symbols count in article: 3.3k | Reading time ≈ 6 mins.

在创建“物业报修系统”项目时,我第一次尝试使用了Maven来创建(基于InteliJ IDEA),在配置Spring的依赖时,手动逐个import各个包,结果在启动JUnit4单元测试时出现以下错误:

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
java.lang.NoSuchMethodError: org.springframework.core.annotation.AnnotationUtils.isInJavaLangAnnotationPackage(Ljava/lang/annotation/Annotation;)Z

at org.springframework.test.util.MetaAnnotationUtils.findAnnotationDescriptor(MetaAnnotationUtils.java:117)
at org.springframework.test.util.MetaAnnotationUtils.findAnnotationDescriptor(MetaAnnotationUtils.java:88)
at org.springframework.test.context.support.ActiveProfilesUtils.resolveActiveProfiles(ActiveProfilesUtils.java:80)
at org.springframework.test.context.support.AbstractTestContextBootstrapper.buildMergedContextConfiguration(AbstractTestContextBootstrapper.java:367)
at org.springframework.test.context.support.AbstractTestContextBootstrapper.buildMergedContextConfiguration(AbstractTestContextBootstrapper.java:305)
at org.springframework.test.context.DefaultTestContext.<init>(DefaultTestContext.java:67)
at org.springframework.test.context.TestContextManager.<init>(TestContextManager.java:103)
at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.createTestContextManager(SpringJUnit4ClassRunner.java:124)
at org.springframework.test.context.junit4.SpringJUnit4ClassRunner.<init>(SpringJUnit4ClassRunner.java:115)
at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:62)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:45)
at java.lang.reflect.Constructor.newInstance(Constructor.java:408)
at org.junit.internal.builders.AnnotatedBuilder.buildRunner(AnnotatedBuilder.java:29)
at org.junit.internal.builders.AnnotatedBuilder.runnerForClass(AnnotatedBuilder.java:21)
at org.junit.runners.model.RunnerBuilder.safeRunnerForClass(RunnerBuilder.java:59)
at org.junit.internal.builders.AllDefaultPossibilitiesBuilder.runnerForClass(AllDefaultPossibilitiesBuilder.java:26)
at org.junit.runners.model.RunnerBuilder.safeRunnerForClass(RunnerBuilder.java:59)
at org.junit.internal.requests.ClassRequest.getRunner(ClassRequest.java:26)
at org.junit.internal.requests.FilterRequest.getRunner(FilterRequest.java:31)
at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:98)
at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:42)
at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:234)
at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:74)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:483)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)


Process finished with exit code -1

我调试了半天,没发现代码里有错误,于是谷歌一下,有人说是包不兼容云云,我心里真是狗粮咧(那么多包都认识我,但我不认识它们,要在几十个包里解决包不兼容问题,这也太难了吧-_-)。

于是乎,我重新创建了一个项目,一次性编写完Spring的依赖,让InteliJ IDEA用Maven的方式帮我引入各个包,再次启动JUnit4的单元测试,得到了测试通过的提示…

适配器(设计模式)

Posted on 2016-05-27
Symbols count in article: 964 | Reading time ≈ 2 mins.

适配器模式之所以存在,和不同手机充电线的接头互不相同是一样的。

比如说,假设现在只有一个带标准USB插口的充电器,怎么样才既能给Android手机充电,又能给iPhone充电呢?答案当然是使用不同的充电线,一条有micro接口,一条有雷电接口。也就是说,我们使用充电线后,虽然仍旧是使用标准USB接口充电,但实际上负责传电的已经变成了micro usb接口和雷电接口,充电线其实就是个另类的适配器。

再举个例子:

假设我们现在有个类son,实现了Eat接口,Eat接口里有EatFood方法,同时还有一个外部类mother(内部聚合了一个son版Eat接口),mother会调用Eat接口的EatFood方法,让son去吃饭。现在mother让son去吃饭时再带上一个女孩一起吃(绝对是亲生的的有木有),但不允许修改son和Eat接口,这时怎么办?(要求是不改变原有接口的同时,还能使用新功能)

这时我们可以创建一个撩妹版son(handSomeSon),他也实现了Eat接口,他在实现EatFood方法时,偷偷地在调用了另一个新接口EatWithGirl的EatFoodWithGril方法,这样一来,mother(内部聚合了一个handSomeSon版Eat接口)还是调用Eat接口的EatFood方法,撩妹版son就和妹子去吃饭去了。也就是说,我们不改变原有接口Eat,却使用到了新接口EatWithGirl的功能。

至于适配器模式的优缺点,可以总结如下。

优点

  • 将目标类(mother)与适配者类(EatWithGirl接口)解耦,并不直接连通。
  • 代码灵活性和扩展性都非常好,符合开闭原则。
  • 类适配器模式(handSomeSon继承自实现了EatWithGirl接口的类)有个优点,可以在适配器handSomeSon中修改实现了EatWithGirl接口的类的方法,适配器更加灵活。
  • 对象适配器模式(handSomeSon内部有实现了EatWithGirl接口的类的对象实例)有个优点,可以同时适配实现了EatWithGirl接口的类和该类的子类。

缺点

  • 类适配器模式的缺点正好和对象适配器的优点相反,而对象适配器模式的缺点正好和类适配器的优点相反。
  • 适配器可能会有许多子类(对象适配器)或许多适配器类(类适配器)

JDK源代码之Vector

Posted on 2016-05-27
Symbols count in article: 2.2k | Reading time ≈ 4 mins.

Vector是和HashTable一个时代的容器,拥有支持同步的特点(各个方法前一律加上synchronized关键字)。后来不支持同步的ArrayList替代了Vector,日渐流行,也正是因为这个原因,Vector和ArrayList的内部实现都差不多。

具体的源码我就不一一注释,只放出让我觉得有意思的方法。

Vector默认的容量是10,扩容时加上一个capacityIncrement或直接翻倍。

System.arraycopy与Arrays.copyOf

我在研究源码时,发现Vector里间替地使用以上2个方法,它们究竟有什么差别呢?
翻出Arrays.copyOf的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")

// 利用反射机制创建一个新的数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);

// copyOf依旧调用System.arraycopy
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

可见,copyOf也会调用arraycopy,而且会创建一个新的数组。
而arraycopy会调用系统底层的复制方法,不同系统的arraycop是不同滴。

removeElementAt(int index)与insertElementAt(E obj, int index)

以上2个方法都会调用系统底层的数组复制函数,复杂度都是O(n)。

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
// 删除元素
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;

// GC优化
elementData[elementCount] = null; /* to let gc do its work */
}

// 增加元素
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
// 调用系统底层的arraycopy
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}

synchronized

Vector之所以与ArrayList不同,支持同步,完成是多亏了synchronized这个关键字。
Vector和HashTable一样,虽然支持同步,但却被抛弃了。

JKD源代码之HashTable

Posted on 2016-05-26 | Edited on 2016-05-27
Symbols count in article: 4.8k | Reading time ≈ 8 mins.

HashTable是个比较古老的实现,现在已经不推荐使用,虽然它比HashMap多了支持同步,但在同步并发方面ConcurrentHashMap更强,而不考虑同步的话,HashMap效率比它高了不少,正如官方注释一样:“If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.”

在get()/put()/remove()等方法上,HashTable都加上了synchronized关键字,以此来实现同步,但熟悉JVM的童鞋都知道,synchronized关键字的代价很高,涉及到内核态和用户态的切换,所有HashTable的效率比较低。

在计算数组下标时,HashTable用了相对比较简单的求模运算,而不像HashMap那样做了移位优化:

1
int index = (hash & 0x7FFFFFFF) % tab.length;

获取:public synchronized V get(Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 计算出数组下标
int index = (hash & 0x7FFFFFFF) % tab.length;
// 遍历该链,找到哈希码和key都相同的元素
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}

可见,HashTable内部在处理冲突时,只是单纯地用链来实现,而不像HashMap一样,在冲突过多时,使用红黑树来优化。

添加:public synchronized V put(K key, V value)

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
public synchronized V put(K key, V value) {
// Make sure the value is not null
// 不允许value为空
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 遍历现有元素,如果有相同的key,就替换
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}

// 如果不存在相同的key,就往里边插入一个新的key
addEntry(hash, key, value, index);
return null;
}

HashTable不允许空的key,也不允许空的value。

添加一个新的键值对:private void addEntry(int hash, K key, V value, int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private void addEntry(int hash, K key, V value, int index) {
modCount++;

Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();

tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}

// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
// 将新的键值对插到链头
tab[index] = new Entry<>(hash, key, value, e);
count++;
}

在这里可以看出,当有新的冲突出现时,新的冲突会插在链头(也许是用了程序局部性原理)

删除:public synchronized V remove(Object key)

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
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 找到数组下标
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
// 寻找待删除的键值对
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
// 如果不是链头
if (prev != null) {
prev.next = e.next;
// 处在链头
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}

重散列算法:protected void rehash()

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
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;

// 同样,容量扩大一倍(默认容量是11)
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;

// 从后往前遍历旧数组
for (int i = oldCapacity ; i-- > 0 ;) {
// 遍历该下标处的冲突链
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;

// 计算新下标
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
// 插入新数组
newMap[index] = e;
}
}
}

JDK源代码之HashMap

Posted on 2016-05-26
Symbols count in article: 15k | Reading time ≈ 26 mins.

HashMap首先是一种Map结构,将一个key映射到一个value,有点特殊的是,HashMap不仅允许value为空,也允许key为空。

其次,HashMap继承自抽象map,而不是像HashTable那样继承自Dictionary(虽然都实现了Map接口);另外,HashTable是同步的,而HashMap并不支持同步。

HashMap内部使用了Hash机制,该机制可以有效地将add与get的平均复杂度降低为O(1)(以前get在最坏的情况下会是O(n),现在当哈希码相同的同一条链上元素数目超过8时,该链会转为平衡树,所以最坏的情况下是O(logN))

重要字段

默认容量:DEFAULT_INITIAL_CAPACITY

HashMap的默认容量,初始值设为16。初始值的设置是有讲究的,必须是2的N次方形式,为什么?在为key计算下标时,我们需要让key的哈希码和数组容量做与运算,2的冥可以使得数据更加分散。

最大容纳因子:loadFactor

HashMap的饱和比例,默认为0.75,当HashMap中的数据量达到75%时,HashMap会启用resize()方法扩大容量,扩大为之前的2倍,也就是newCap = oldCap << 1。

节点数组:Node<K,V>[] table

可见HashMap内部其实使用了数组,节点数组,每个Node节点是一个键值对,各个键值对之间通过next指针相连在一起。

Node的源代码如下:

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
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;

Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }

// 每个键值对的哈希码也是独一无二的
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}

// 更换该键值对的值
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

// 判断两个键值对是否equals,不仅key要相同,而且value也要相同
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}

Set<Map.Entry<K,V>> entrySet

存储键值对的一个set集合,它和上面的table有什么区别?似乎被抛弃了,因为已经有了entrySet()方法。

size

HashMap内部数据的大小。

threshold

size的数值超过它时,HashMap必须扩容。

重要方法

计算哈希码:static final int hash(Object key):

1
2
3
4
5
6
7
static final int hash(Object key) {
int h;

// 如果对象为空则返回0
// 如果不为空,就求得key.hashCode()的结果h,将h与其左移16位后的结果做异或。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里为什么要和左移16位的结果呢?官方是这样解释的:“Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide.”。
原来,这是为了减小冲突,把高位的数据扩散到低位。举个例子,假设HashMap的数组大小是16,那么计算出来的哈希码必须和16(二进制是4个1)做与的运算,这样一来,哈希码只有低4位才起作用,如果有大量的key的哈希码的低4位都相同而更高位不同,它们最终依旧会放在同一个下标,哪怕它们之间因为高位不同而差别巨大。

扩容并重散列:final Node<K,V>[] resize()

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
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {

// HashMap原先的容量已经达到极限,无法扩容,直接返回旧的table
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}

// 将容量直接翻倍,“可用容量”也翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

// 在HashMap为空的情况下进行扩容,初始化各项参数
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

// 得到新的table数组,大小是原先的两倍
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {

// 逐项扫描旧table数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;

// 如果旧tabel数组的某一下标处不为空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;

// 如果该下标处只有一个元素,而没有因哈希码相同而处在同一条链上元素
if (e.next == null)
// 直接放入新的table数组。因为数组容量扩大一倍,有可能下标是之前的两倍,也有可能不变
newTab[e.hash & (newCap - 1)] = e;

// 如果该下标处的元素是一个树节点。(哈希码冲突的key都放在同一棵树上,树根放在该哈希码对应的数组下标处)
else if (e instanceof TreeNode)
// 将旧的树分裂,放到新的数组中去
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

// 如果同一链中数据不到8个(仍未分裂为树),则将旧链分为2条新链
else { // preserve order

// 下标较小的新链(low)
Node<K,V> loHead = null, loTail = null;
// 下标较大的新链(high)
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 之前都是与oldCap-1(假设二进制有4位)做与运算,结果是4位二进制,如今与oldCap
// (有5位,且最高位为1其余为0)做运算,第5位是0的到下标低的新链,第5位是1的到下标大的新链
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);

// 将两条新链加入新table数组
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

该方法处理的数组下标处元素有以下3种情况:

  1. 该下标处不存在冲突的数据
  2. 该下标处存在冲突的数据,冲突的数据不够多,用一条链来存储(新的冲突的数据不再放在链头部,而是放在链尾部)
  3. 该下标处存在冲突的数据,冲突的数据特别多,用一棵平衡树来存储

该方法是HashMap中极为重要的方法,处理HashMap扩大容量时的各种情况。

关于该方法的性能:

  1. 如果是第一种情况,复杂度当然是O(1)
  2. 如果是第二种情况,复杂度是该链的长度,最差情况下会达到O(n)
  3. 如果是第三种情况,那么复杂度和红黑树的遍历有关,在下面分析到树的分裂时再具体分析。搜索插入删除的复杂度都能做到O(logN)。

插入:final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict):将一个键值对插入HashMap

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
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;

// 如果旧table数组为空,就需要调用resize方法来扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;

// 哈希码与数组大小做与运算,寻找合适的下标。
// 如果该下标处为空,就新建一个Node节点.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);

// 该下标已经有元素存在
else {
Node<K,V> e; K k;
// 该下标的元素的key就是要插入的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 该下标的元素是个树节点(说明哈希码冲突的key过多,已经被逼用红黑树结构来存储)
else if (p instanceof TreeNode)
// 插入到该哈希码对应的红黑树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 该下标的元素是条链的链头
else {
// 遍历该链,力图插入到链尾
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果该链的长度达到一定长度,就转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 该链中已经有该key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 插入后,考虑是否要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

该方法会将一个键值对插入到HashMap,哈希码由hash()方法计算得到。

和resize()方法类似,在插入键值对时也要分情况考虑:

  1. 如果数组下标处为空,则直接插入一个Node节点
  2. 如果数组下标处不为空,且是一个树节点,则插入键值对到该下标对应的红黑树中去
  3. 如果数组下标处不为空,且是一条链的链头,则尝试插入到链尾
  4. 在这过程中,如果key已经存在则返回

在插入后还要考虑是否要扩容。

获取value:final Node<K,V> getNode(int hash, Object key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

// 确保数组不为空,且根据该哈希码计算得到的下标处不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 该下标处就是我们要找的key
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果该节点是树节点,则遍历对应的红黑树
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 如果不是树节点,说明是链结构,直接遍历该链
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

getNode方法根据key的哈希码和key来查找相应的value。
同样的,该方法也会分情况讨论。

删除:final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

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
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}

// 分情况,将该节点删除
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}

想要删除一个节点,首先要查找到该节点,事实上,该方法中的搜索过程和getNode一模一样。
找到后,也是根据数组下标处元素的不同来分情况,这里不再赘述。

static final int tableSizeFor(int cap):对一个整数,求出大于它且最接近它的2的冥

1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

该方法非常巧妙,将最高位的1不断地置换到所有地位上去(结果类似于000011111111),最终加1,记得到2的冥次(也就是000111111111)。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict):将一堆数据插入HashMap

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
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {

// 如果HashMap数组为空,没有元素
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);

// 当前设置的“可用容量”不够,扩大“可用容量”。
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();

// 将m中的键值对都插入HashMap
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit):将旧数组上的树分裂到新数组上去

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
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}

if (loHead != null) {
// 如果新的低链数量不够,就只形成一条链
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);

// 如果数量很多,就将链转为红黑树
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
// 如果新的高链数量不够,就只形成一条链
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
// 如果数量很多,就将链转为红黑树
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}

树的分裂,其复杂度似乎也是O(n)?将链转为树时涉及到红黑树的插入平衡等调整,尚未接触红黑树,待日后补充。

总结:不同于以前HashMap单纯用链来处理冲突,现在的HashMap引入了红黑树来应付大量的冲突,HashMap的效率提高了不少,当n是一百万时也可以接受,至少在最坏情况下复杂度不再是O(n)。

Object源码(JAVA)

Posted on 2016-05-25
Symbols count in article: 1.2k | Reading time ≈ 2 mins.

我们都知道,JAVA是门面向对象语言,也就是说,JAVA中对象的地位是极高的。

遍观JDK源码,所有的类都继承自始祖级别的类:Object类。

Object类内部的方法有如下这些:

方法 说明
getClass() 获得该对象的Class类对象
clone() 克隆一份新对象,两个对象不==,但equals
toString() 以字符串形式,输出对象信息
hashCode() 获得该对象的哈希码
equals() 判断两个对象内容是否相等
finalize() 用于GC,当算法将该对象放入待清除队列后会尝试调用该方法一次
wait() 使得当前线程释放该对象的锁,让该对象恢复自由
notify() 唤醒一个等待该对象的线程,使得该对象被线程拥有
notify() 给所有等待的线程发去唤醒消息

源码

  1. toString():该函数仅仅打印出对象所属的类+‘@’+对象哈希码

    1
    2
    3
    public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
    }
  2. equals():平时我们说==与equals是不同的两种东西,但这里的equals内部就是用了==来作比较。

    1
    2
    3
    public boolean equals(Object obj) {
    return (this == obj);
    }
  3. hashCode():这里Object的hashCode方法没有实现,可以看一下String的hashCode是怎么实现的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    // 以下是String的hashCode()
    public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    char val[] = value;

    for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
    }
    hash = h;
    }
    return h;
    }

可见String在计算哈希码前会尝试返回上一次已经计算出来的结果,为什么要乘以31再加上字符的ANSC码呢?

  • 第一,乘上一个数是为了分权重(越在前面的字符在哈希码中权值越大,这使得前缀相同长度相同的字符串的哈希码差不多大,可以存放在相邻的地方)。
  • 第二,乘上31是因为31是素数,可以增大结果的唯一性。

从0到1理解JVM垃圾回收机制

Posted on 2016-05-22
Symbols count in article: 2.1k | Reading time ≈ 4 mins.

从C++转到JAVA,首先要知道的一条是,JAVA拥有相对比较完善的内存垃圾回收机制(回想以前在中大的作业平台上写C++代码,在new之后总会忘记free,导致我每次都不能开开心心地AC,巨汗-_-!)

JAVA是一门半编译半解释的语言,在编译阶段无法确定回收垃圾的具体位置(虽然有部分是可以确定的),所以回收垃圾的任务主要交由JVM来处理,我们经常听到高手们谈到的所谓GC指的就是垃圾回收。

垃圾回收主要有两步:

  • 识别哪些是垃圾
  • 使用回收的算法将垃圾‘扫入’垃圾桶

谁是垃圾

在之前的博文里,我们知道JAVA运行时主要分程序计数器、虚拟机栈、本地方法栈、堆、方法区。前3者随着线程同生共死,当线程结束时,它们的内存就被回收了,只有剩下的堆和方法区需要我们竭尽全力地进行垃圾回收。

那么,在堆和方法区里,我们怎么知道谁是垃圾呢?

寻找垃圾算法之引用计数法

熟悉操作系统的童鞋都知道,引用计数算法的主要思想是:当有个地方引用了某个对象时,该对象的计数器增加1,当那个地方不再引用该对象时,该对象的计数器减1;直到计数器的值为0,系统就认为该对象不再有用,把它标记为垃圾。

一个论文引用的例子可以解释该算法:假设你是个德高望重的学者,你写了篇影响巨大的论文,那么你的论文理所当然会被许多人引用和参考,因为你的论文特别有价值;相反,如果你是个三流的研究人员,你写的东西无人问津,就会被视为“垃圾”。

这个算法最大的缺点是:它无法处理相互循环引用的情况。什么意思呢?

还是论文引用的例子:假设现在有3个三流的研究人员A、B和C,他们分别写出了3篇质量极其低下的论文,按理来说,他们的论文是“垃圾”,不会被人引用,但数据显示,3篇论文的被引用数都为1。相关部门调查后发现,A引用了B的论文,B引用了C的论文,而C又引用了A的论文,所以虽然3篇全都是“垃圾”,但却存在着彼此的引用,形成了一个环,使得人们认为3篇论文不是“垃圾”,逃过了被“回收”的危险。

因为这个缺点,引用计数法基本只作为反例,只存在于教科书上。

寻找垃圾算法之可达性分析算法

可达性分析的原理是:一个对象引用了另一个对象时,两个对象之间就存在连线,理清了所有的对象的引用关系之后,它们基本都会处在同一颗树上,此时,将不在树上的对象视为垃圾。也就是说,那些无人知晓的对象都是垃圾。

这个算法的关键点是:从谁开始找呢?

(如果从垃圾开始找,那么那些不是垃圾的反倒视为垃圾,这是极为严重的噩梦!)

有种对象,它的价值比较大,不会被轻易抛弃,相对稳定,存在的时间较长,被称为GC Roots,是可达性分析算法的起始点。GC Roots一般只存在于栈和方法区中(具体是虚拟机栈中局部变量表内引用的对象、本地方法栈中Native方法引用的对象和方法区中静态变量和常量引用的对象),堆中不会有。

清除垃圾的强有力手段

知道谁是垃圾,下一步是启用算法将其清除。也许有人会笑,清除内存中的垃圾有什么难的,直接将它标记为废弃不就得了嘛,还在那边唧唧歪歪的整啥呀?

标记清除算法

这个算法和上面说的“直接标记为废弃”一模一样,先扫描一遍,利用可达性分析算法,将垃圾标记出来,再扫描一遍,将垃圾清除。

这个算法太简单了,简单到不是计算机专业的人也能秒懂,但它的简单也导致了极为复杂的后果:在一整段内存上,将其中的几个地方标记为废弃,会使得这条内存看起来‘坑坑洼洼’的,也就是内存碎片。碎片一多,分配内存时就不能顺利地拿到一块大内存(毕竟内存条上只有细小的碎片)。

为了解决这个碎片的问题,人们又想到了一个方法。

标记复制算法

这个算法的标记阶段和标记清除算法一样,差别在于,它不再清除无用的内存,而是将有用的内存复制到另一片空间,剩下的这片空间称为未拆封全新区域。

举个例子,对于一块1G的内存,我们将它划分为2块512M的小内存,每次我们只使用其中一块;在垃圾回收时先找出垃圾,然后将不是垃圾的对象移动到另一块内存上,并将这一块内存清空;下一次进行回收时也是同样的原理。

但这个算法也有一个缺点:任何时候都有一块内存不会被用到,也就是说,内存被浪费了。

幸好,这个缺点可以减弱到能被接受的程度。(既然每次都会浪费掉一块内存,那么,我们每次都只浪费一块非常小的内存不就行了吗?)

标记整理算法

标记出垃圾后,既不直接将其清除,也不将有效对象复制到另一块内存上,而是将有效对象复制到内存的开头,如此一来,既不会导致过多碎片,也不会浪费另一块内存。

分代收集算法

上面三个算法都仅考虑对现有垃圾的回收,未曾考虑到时间这个不可避免的因素在垃圾回收中的影响,所以现代的虚拟机都使用一种被称为“分代收集”的算法来进行实际的垃圾回收。分代收集的原理是:根据对象的已存活时长,将其划分到不同区域,在不同区域里采取不同的回收算法。

一般来说,虚拟机会将堆分为2个年代:

  • 新生代
  • 老年代

在新生代里使用了标记复制算法,所以新生代又分为3个区域:

  • 一个eden亚当区(占80%空间):这个区里存放着大量鲜活的年轻对象,它们中只有少数会存活下来。
  • 两个survivor幸存者区(各占10%空间):这个区里存放的对象已经有了一定年纪,它们的部分人可能有机会迁往老年代进行养老。

从0到1理解JVM内存分配机制

Posted on 2016-05-22
Symbols count in article: 945 | Reading time ≈ 2 mins.

在JAVA中,除了在即时编译器优化后部分对象会在栈上分得足够空间,其余的对象都会在堆上“求分配空间”,所以之前我们才说,堆里存在着大大小小密密麻麻的对象。

那么在堆里,对象究竟会分到哪部分的内存,新生代还是老年代?

普通对象

答案是:对象一般会分配到新生代中Eden区的内存。

一个普通对象的极端经历

有新对象到来,而Eden又没有足够的空间时,新生代尝试进行新生代的垃圾回收(也就是Minor GC)。在尝试之前,它需要知道,如果情况特别糟糕,这次Minor GC是否安全,也就是新生代所有对象都必须移到老年代以便腾出空间存放新对象,换句话说,新生代会问老年代:“你还有连续空间可以存放我现在的崽崽们吗”,如果老年代给他个肯定,新生代就可以无忧无虑地进行Minor GC了。

如果老年代没有给出肯定答案,新生代就会再问一句:“在以往迁往你那边的对象大小里,取个平均值,你现在还有那么大的连续空间吗?”如果老年代回答yes,新生代就认为接下来的Minor GC的对象有极大的可能小于历史平均值,可以冒些风险进行MinorGC(风险是接下来的对象确实超过了历史平均值,老年代没有连续空间存放新生代来的对象,老年代需要进行老年代的回收也就是Full GC,因为新生代的冒险进行了一次失败的Minor GC,老年代需付出Full GC的代价,而后新生代再重头尝试Minor GC)。当然了,如果老年代说了不,那么新生代就得先等老年代执行了Full GC再执行新生代专属的Minor GC。

那些超大的对象

如果对象十分非常极其以及特别的巨大,那么新生代会直接请求老年代的帮助,将对象分配在老年代(老年代人太好了,新生代装不下的对象它负责装。)

一群长寿的对象

如果对象太老,也就是说在Eden区呆了一代,又在Survivor存活期呆了15代(默认是15代),那么该对象会迁往老年代,可见,JVM的世界里,一个对象的退休年龄是16。

一群稳定的幸存者

Survivor区中的对象不必等15代才能迁往老年代。如果某一年纪的对象的所占空间超过Survivor区大小的一半,它们会被赶走,赶到老年代。那种年纪的对象有这么多一起存活了这么长时间,JVM默认它们这一代的稳定性都比较好,可以提前去老年区过稳定的生活。

从0到1理解JVM运行时数据区

Posted on 2016-05-18
Symbols count in article: 1.9k | Reading time ≈ 3 mins.

与操作系统类似,JVM(JAVA虚拟机)拥有自己的运行时数据区。在操作系统中,通常有代码区、数据区、堆、栈和静态区等,而JVM中的数据区则有所不同(虽然JVM号称虚拟机,是机器,但它和现实机器始终还是有差别的)。

JVM的运行时数据区类型有下面5种:

类型 属于 抛出异常类型
程序计数器 线程私有 无
虚拟机栈 线程私有 SOF、OOM
本地方法栈 线程私有 SOF、OOM
堆 公有 OOM
方法区 公有 OOM

程序计数器

程序计数器和CPU中的PC寄存器起着同样的作用:保存下一条指令的地址。不同的是,CPU中的PC寄存器是共有的,JVM中的程序计数器是线程私有的,每个线程都需要一个程序计数器来记住自己已经执行到哪儿了,线程之间轮流执行一段时间,轮到自己时,就可以借助程序计数器从正确的地方往下执行。

虚拟机栈

顾名思义,该栈属于JVM,用来保存一些必要的数据。熟悉操作系统的人都知道,在执行一个方法时,系统会将返回地址和形参等压入栈,执行过程中会从栈里获得形参,执行完方法的全部指令后再从栈中获得返回地址以便跳出方法。

虚拟机栈的原理也是一样的,在准备执行一个方法时,JVM会为该方法生成一个栈帧,将栈帧压入栈;在执行方法的过程中,JVM借用该栈帧搞一些动作;执行完方法后将该栈帧出栈。也就是说,虚拟机栈主要是服务于方法们的执行过程的,一个方法的诞生需要虚拟机栈,一个方法的死亡也需要虚拟机栈,虚拟机栈是多么的有爱和有担当。

虚拟机栈的栈帧中都有些什么玩意呢?

  • 局部变量表:这玩意可不得了,它保存了一个方法执行过程中所需要的所有局部变量!比如说,我们在一个save()方法里定义了一个int类型的temp变量,每次执行save()时,temp都会出现在局部变量表中。更不得了的是,局部变量表的大小在编译时就固定了!不过值得注意的是,该表中只存放变量,不存放对象。
  • 返回地址:也就是俗话中的“return到哪儿去”。
  • 操作数栈:熟悉计算机组成原理或编译原理的童鞋都知道,虽然现代计算机很多都是基于寄存器,但在很早以前曾有一种基于栈的机器,后来因效率问题基于栈的设计被弃用。而JVM,恰恰就是一种基于栈的设计。写过基于栈的四则计算器的同志都知道操作数栈是什么玩意。
  • 动态链接:我还不是特别明白动态链接,以后再回来补充。

因为该区基于栈结构,所以不可避免在极端情况下会出现栈溢出(SOF);另外呢,该区的大小是可以动态扩展的,有时候机器没有多余供其扩展,供其挥霍,也就不可避免地出现内存不足(OOM)。

本地方法栈

随着时代的进步,JAVA的执行效率在逐渐地提升,JAVA已经能够做到在合适的时候“调用操作系统的本地方法,以一种C或C++的速度去执行”。那么在执行系统本地方法时,本地方法也需要栈呀,这些栈在哪里呢?不太可能复用虚拟机栈吧(虚拟机栈专门服务于JAVA语言)。应该在哪里设置个栈呢?为了解决这个问题,聪明的人类推出了本地方法栈,它是属于本地方法的栈。

堆

堆是什么呢?熟悉C语言的同学都知道,在C中动态申请一块空间需要使用malloc函数,该函数将在堆里获得空间,这里的堆和JVM中的堆其实也是差不多的。
JVM中的堆,主要用于内存的动态分配。一个对象需要内存时,主要从堆中申请到(注意我用了‘主要’,现如今有栈上分配等技术可以给对象分配内存)。简单地说,堆中充满了大大小小密密麻麻的对象。

由于对象主要都在堆里,当一个对象不再有用时,我们可以将它从堆里抹除,这种做法叫做垃圾回收,英文名叫GC。

出于现代垃圾回收器的需要,堆通常被分为新生代(内含一个EDEN区和两个Survivor区)和老生代。垃圾回收器不断地监视着堆里的众多对象,看谁不爽就把谁KO,将之扼杀于堆中。

堆存放了所有线程的对象,它顺理成章地成为公共区域。

方法区

方法区是运行时数据区中的最后一个,它存放的主要是运行时的代码。当一个类被加载时,它会从class文件里被加载到方法区中,它的类版本、字段信息、方法信息、接口信息和常量池都会被加载到方法区中。除了存放类的信息,方法区还存放常量、静态变量和代码。也就是说,方法区中的内容大部分都是不变的,除了一个叫做常量池的奇葩。

常量池里边主要是符号引用和直接引用(不明白这两个概念的可以将它们看作一条条的字符串,如“hi”,“hello”等),之所以说常量池会变化,是因为运行时产生的常量也可以加入常量池。

将JVM的运行时数据区和操作系统的运行时数据区做比较,结果如下

JVM 操作系统
程序计数器 PC寄存器
虚拟机栈、本地方法栈 栈
GC堆 malloc堆
方法区 代码区

JDK源代码之LinkedList

Posted on 2016-05-18
Symbols count in article: 9.7k | Reading time ≈ 16 mins.

LinkedList特性

底层数据结构

LinkedList不同于ArrayList的数组,它基于链表。

效率

LinkedList的插入删除快,遍历慢(ArrayList正好相反)

实现的接口

1
2
3
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList实现了List接口、Deque双向队列接口(既可以当作FILO队列也可以当作FIFO栈)、Cloneable接口、序列化接口。
值得注意的是,LinkedList继承自AbstractSequentialList(AbstractSequentialList和ArrayList一样继承自AbstractList),也就是说,LinkedList比ArrayList更细化了一层。

细化的那层AbstractSequentialList实现了“链表”版的get/set/add/remove方法,这使得LinkedList和ArrayList有了质的差别(毕竟彼此的基因遗传都不同)。

同步机制

与ArrayList一样,LinkedList也是不同步的,可以用包装器来创造一个支持同步的List:

1
List list = Collections.synchronizedList(new LinkedList(...));


LinkedList字段

1
2
3
4
5
transient int size = 0;

transient Node<E> first;

transient Node<E> last;

很明显,LinkedList用了first节点和last节点来保存整个链表(ArrayList用的是数组)。
注:transient关键字的作用是防止该字段被序列化(一些敏感的信息不能序列化然后在网络上传输)。


LinkedList方法分析

linkFirst(E e) (将一个元素插入链表头部)

1
2
3
4
5
6
7
8
9
10
11
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}

先建立一个以first为后继的新节点,令first为该新节点;然后再修改第二个节点的prev变量使其指向新头部(如果没有第二个节点就修改last)

linkLast(E e)(将一个元素插入链表尾部)

机制与linkFirst(E e)相似,只需将first替换为last

linkBefore(E e, Node succ) (将一个元素插到一个节点之前)

1
2
3
4
5
6
7
8
9
10
11
12
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

该方法会判断另一个节点之前是否有节点存在,没有就修改first。

unlinkFirst(Node f)(将链表头部节点剔除)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}

该方法中有条垃圾回收优化的语句:

1
f.next = null; // help GC

强行令变量为null,不再引用该对象,该对象便会在下一轮的GC中被回收。
此外,该方法会判断第二个元素是否存在,没有就修改last。

unlinkLast(Node l)(将链表尾部节点剔除)

与unlinkFirst(Node<E> f)类似

unlink(Node x)(剔除某个特定的节点)
Read more »

JDK源代码之ArrayList

Posted on 2016-05-17 | Edited on 2016-05-18
Symbols count in article: 75k | Reading time ≈ 2:05

ArrayList的特性

实现的接口

ArrayList的类声明如下:

1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

轻轻一撇,我们便是可以看出,ArrayList继承自抽象泛型类AbstractList<>,它实现了List接口(Collection集合的List),也拥有RandomAccess/Cloneable/Serializable三个“标注”接口。

同步机制

与Vector相比,ArrayList放弃了同步机制。如果我想要一个支持同步的ArrayList,可以使用Collections工具类中的synchronizedList方法构建一个List:

1
List list = Collections.synchronizedList(new ArrayList(...));

时间空间复杂度

ArrayList的get/size/isEmpty等方法的复杂度均为常数,add方法的复杂度为O(n),其余的都是线性复杂度。

ArrayList字段

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
private static final long serialVersionUID = 8683452581122892189L;

/**
* Default initial capacity.
* ArrayList的默认容量。插满会自动扩充。
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* Shared empty array instance used for empty instances.
* 保存ArrayList元素的空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access

/**
* The size of the ArrayList (the number of elements it contains).
* ArrayList的实际大小(已经插入了多少数据)
*
* @serial
*/
private int size;

ArrayList方法分析

从上往下分析

Read more »

使用Eclipse阅读JDK源码

Posted on 2016-05-17 | Edited on 2016-05-27
Symbols count in article: 165 | Reading time ≈ 1 mins.

研究JDK源代码,是从JAVA新手走向高手的必经之路。阅读JDK源码的方法如下:

  1. 在eclipse中新建一个JAVA工程
  1. 将JDK安装根目录里的src.zip解压到JAVA工程目录下
  1. 回到eclipse,右键点击工程,选择refresh
  1. 此时,除了一堆编译错误外,你应该可以开始阅读JDK所有源码

从无到有写一个后台注册模块(基于SSH2)

Posted on 2016-05-17
Symbols count in article: 22k | Reading time ≈ 37 mins.

此次项目基于SSH2框架(物业报修系统),为了避免忘记框架使用的步骤,我稍微记录一下注册模块的编写过程。

框架分层

核心是Spring框架,它有IOC容器,可以方便地管理Struts2和Hibernate;Struts2因其MVC的架构,因而负责显示;Hibernate则是持久层,实现DAO。

步骤

下面是详细的步骤,根据时间先后一步一步来。

Tomcat容器的配置(WebRoot/WEB-INF/web.xml)

该文件告诉Tomcat,主页是哪个、Action交给谁处理、网站的编码格式、过滤拦截哪些URL、托管给Spring等。

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
<?xml version="1.0" encoding="UTF-8"?>
<web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://java.sun.com/xml/ns/javaee
http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd">

<!-- 所有请求都通过FilterDispatcher查找actionMapper的设置来决定请求对应的是哪个Action -->

<display-name>邱永臣配置</display-name>

<!-- 过滤器的配置 -->
<filter>
<!-- 名字 -->
<filter-name>filterDispatcher</filter-name>
<!-- 过滤器对应的名字 -->
<filter-class>org.apache.struts2.dispatcher.FilterDispatcher</filter-class>
</filter>

<filter-mapping>
<filter-name>filterDispatcher</filter-name>
<!-- 过滤匹配的URL -->
<url-pattern>/*</url-pattern>
</filter-mapping>

<!-- 解决中文乱码问题 -->
<filter>
<filter-name>struts-clean</filter-name>
<filter-class>org.apache.struts2.dispatcher.ActionContextCleanUp</filter-class>
</filter>
<filter-mapping>
<filter-name>struts-clean</filter-name>
<url-pattern>/*</url-pattern>
</filter-mapping>

<!-- 进入WEB应用访问的默认文件 -->
<welcome-file-list>
<welcome-file>lookRemindRepairOrder.jsp</welcome-file>
</welcome-file-list>

<context-param>
<param-name>contextConfigLocation</param-name>
<!-- 如果将该xml文件放在WEB-INF下面的话,就需要下面配置 <param-value>WEB-INF/applicationContext.xml</param-value> -->
<param-value>WEB-INF/applicationContext.xml</param-value>
<!-- 下面是默认配置 -->
<!-- <param-value>classpath:com/lzq/config/applicationContext-*.xml</param-value> -->
</context-param>

<!-- 采用Listener来初始化Spring容器 -->
<listener>
<listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
</listener>
</web-app>

编写用户实体(model层)

所谓用户实体,其实是java bean,它内部有用户数据:

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
/**
*
*/
package com.ilovecl.myproperty.model;

/**
* 学生实体
*
* @author 邱永臣
*
* 对应的数据库建表命令为 create table `Student` ( `userId` int not null primary
* key auto_increment, `userName` varchar(20) not null, `password`
* varchar(20) not null, `phoneNumber` long, `email` varchar(100),
* `sexual` varchar(10)) ENGINE=InnoDB DEFAULT CHARSET=utf8;
*/

public class Student {
private int userId;
private String userName;
private String password;
private long phoneNumber;
private String email;
private String sexual;

public Student() {
super();
// TODO Auto-generated constructor stub
}

public Student(String userName2, String password2, long phoneNumber2,
String email2, String sexual2) {
this.userName = userName2;
this.password = password2;
this.phoneNumber = phoneNumber2;
this.email = email2;
this.sexual = sexual2;
}

/**
* @return the userId
*/
public int getUserId() {
return userId;
}

/**
* @param userId
* the userId to set
*/
public void setUserId(int userId) {
this.userId = userId;
}

/**
* @return the userName
*/
public String getUserName() {
return userName;
}

/**
* @param userName
* the userName to set
*/
public void setUserName(String userName) {
this.userName = userName;
}

/**
* @return the password
*/
public String getPassword() {
return password;
}

/**
* @param password
* the password to set
*/
public void setPassword(String password) {
this.password = password;
}

/**
* @return the phoneNumber
*/
public long getPhoneNumber() {
return phoneNumber;
}

/**
* @param phoneNumber
* the phoneNumber to set
*/
public void setPhoneNumber(long phoneNumber) {
this.phoneNumber = phoneNumber;
}

/**
* @return the email
*/
public String getEmail() {
return email;
}

/**
* @param email
* the email to set
*/
public void setEmail(String email) {
this.email = email;
}

/**
* @return the sexual
*/
public String getSexual() {
return sexual;
}

/**
* @param sexual
* the sexual to set
*/
public void setSexual(String sexual) {
this.sexual = sexual;
}

}

编写Hibernate的映射文件(Student.hbm.xml)

Hibernate正是凭借它,才能将对象映射到数据库中去:

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
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE hibernate-mapping PUBLIC "-//Hibernate/Hibernate Mapping DTD 3.0//EN"
"http://hibernate.sourceforge.net/hibernate-mapping-3.0.dtd">

<hibernate-mapping>
<class name="com.ilovecl.myproperty.model.Student" table="Student">
<id name="userId" type="java.lang.Integer">
<column name="userId" />
<generator class="increment" />
</id>
<property name="userName" type="java.lang.String">
<column name="userName" length="20" />
</property>
<property name="password" type="java.lang.String">
<column name="password" length="20" />
</property>
<property name="phoneNumber" type="java.lang.Long">
<column name="phoneNumber" />
</property>
<property name="email" type="java.lang.String">
<column name="email" length="100" />
</property>
<property name="sexual" type="java.lang.String">
<column name="sexual" length="10" />
</property>
</class>
</hibernate-mapping>

将Hibernate托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码,告诉Hibernate数据库的信息,映射文件的位置,将Hibernate的sessionFactory托管给Spring:

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
<bean id="dataSource" class="org.apache.commons.dbcp.BasicDataSource">
<property name="driverClassName">
<value>com.mysql.jdbc.Driver</value>
</property>
<property name="url">
<!-- 设置字符集,防止插入到数据库里时出现乱码 -->
<value>jdbc:mysql://139.129.118.90:3306/myproperty?useUnicode=true&amp;characterEncoding=UTF-8</value>
</property>
<property name="username">
<value>root</value>
</property>
<property name="password">
<value>test</value>
</property>
</bean>
<bean id="sessionFactory"
class="org.springframework.orm.hibernate3.LocalSessionFactoryBean">
<property name="dataSource">
<ref bean="dataSource" />
</property>
<property name="hibernateProperties">
<props>
<prop key="hibernate.dialect">
org.hibernate.dialect.MySQLDialect
</prop>
</props>
</property>
<property name="mappingResources">
<list>
<value>com/ilovecl/myproperty/model/Student.hbm.xml</value>
</list>
</property>
</bean>

<bean id="baseTransactionProxy"
class="org.springframework.transaction.interceptor.TransactionProxyFactoryBean"
abstract="true">
<property name="transactionManager">
<ref bean="transactionManager" />
</property>
<property name="transactionAttributes">
<props>
<prop key="save*">PROPAGATION_REQUIRED</prop>
<prop key="update*">PROPAGATION_REQUIRED</prop>
<prop key="delete*">PROPAGATION_REQUIRED</prop>
</props>
</property>
</bean>

编写DAO层代码(接口和实现)

DAO层专门操作实体,比如增删改查一个学生等。
接口代码:

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
/**
*
*/
package com.ilovecl.myproperty.DAO;

import java.util.List;

import com.ilovecl.myproperty.model.Student;

/**
* DAO层:学生DAO的接口
*
* @author 邱永臣
*
*/
public interface IStudentDAO {
public abstract void save(Student transientInstance);

public abstract void delete(Student persistentInstance);

public abstract Student findById(java.lang.Integer id);

public abstract List<Student> findByUserName(java.lang.String userName);

boolean isStudentExits(String userName);

}

实现的代码:

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
/**
*
*/
package com.ilovecl.myproperty.DAO.impl;

import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.springframework.orm.hibernate3.support.HibernateDaoSupport;

import com.ilovecl.myproperty.DAO.IStudentDAO;
import com.ilovecl.myproperty.model.Student;

/**
* @author 邱永臣
*
*/
public class StudentDAO extends HibernateDaoSupport implements IStudentDAO {

private static final Log log = LogFactory.getLog(StudentDAO.class);

/*
* (non-Javadoc)
*
* @see
* com.ilovecl.myproperty.DAO.IStudentDAO#save(com.ilovecl.myproperty.model
* .Student)
*/
@Override
public void save(Student transientInstance) {
log.debug("save(Student transientInstance) in StudentDAO");
try {
this.getHibernateTemplate().saveOrUpdate(transientInstance);
log.debug("save(Student transientInstance) in StudentDAO successful");
} catch (RuntimeException re) {
log.error("save(Student transientInstance) in StudentDAO failed",
re);
throw re;
}

}

/*
* (non-Javadoc)
*
* @see
* com.ilovecl.myproperty.DAO.IStudentDAO#delete(com.ilovecl.myproperty.
* model.Student)
*/
@Override
public void delete(Student persistentInstance) {
log.debug("delete(Student persistentInstance)");
try {
getHibernateTemplate().delete(persistentInstance);
log.debug("delete(Student persistentInstance) successful");
} catch (RuntimeException re) {
log.error("delete(Student persistentInstance) failed", re);
throw re;
}

}

/*
* (non-Javadoc)
*
* @see com.ilovecl.myproperty.DAO.IStudentDAO#findById(java.lang.Integer)
*/
@Override
public Student findById(Integer id) {
log.debug("findById(Integer id) : " + id);
try {
Student instance = (Student) getHibernateTemplate().get(
"com.ilovecl.myproperty.model.Student", id);
return instance;
} catch (RuntimeException re) {
log.error("findById(Integer id) failed", re);
throw re;
}
}

/*
* (non-Javadoc)
*
* @see
* com.ilovecl.myproperty.DAO.IStudentDAO#findByUsername(java.lang.Object)
*/
@SuppressWarnings("unchecked")
@Override
public List<Student> findByUserName(String userName) {
List<Student> students;
try {
String queryString = "from Student as model where model."
+ "userName" + "= ?";
students = getHibernateTemplate().find(queryString, userName);
} catch (RuntimeException re) {
log.error("findByUserName failed", re);
throw re;
}

return students;
}

@Override
public boolean isStudentExits(String userName) {
return findByUserName(userName).size() == 1;
}
}

将DAO托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码:

1
2
3
4
5
6
<!-- 将学生DAO托给Spring -->
<bean id="studentDAO" class="com.ilovecl.myproperty.DAO.impl.StudentDAO">
<property name="sessionFactory">
<ref bean="sessionFactory" />
</property>
</bean>

编写逻辑层代码(接口与实现)

逻辑层原先放在Struts2控制层的Action中,但随着Action的日渐庞大,许多负责的逻辑代码需要分离出来单独作为逻辑层。

接口的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
*
*/
package com.ilovecl.myproperty.service;

import com.ilovecl.myproperty.DAO.IStudentDAO;
import com.ilovecl.myproperty.model.Student;

/**
* @author 邱永臣
*
*/
public interface IRegisterService {

public IStudentDAO getStudentDAO();

public void setStudentDAO(IStudentDAO studentDAO);

public boolean register(Student student);

boolean isStudentExits(String userName);
}

实现的代码:

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
/**
*
*/
package com.ilovecl.myproperty.service.impl;

import com.ilovecl.myproperty.DAO.IStudentDAO;
import com.ilovecl.myproperty.model.Student;
import com.ilovecl.myproperty.service.IRegisterService;

/**
* @author 邱永臣
*
*/
public class RegisterService implements IRegisterService {

private IStudentDAO studentDAO;

/**
* @return the studentDAO
*/
public IStudentDAO getStudentDAO() {
return studentDAO;
}

/**
* @param studentDAO
* the studentDAO to set
*/
public void setStudentDAO(IStudentDAO studentDAO) {
this.studentDAO = studentDAO;
}

/*
* (non-Javadoc)
*
* @see
* com.ilovecl.myproperty.service.IRegisterService#isStudentExits(java.lang
* .String)
*/
@Override
public boolean isStudentExits(String userName) {
return studentDAO.findByUserName(userName).size() == 1;
}

/*
* (non-Javadoc)
*
* @see
* com.ilovecl.myproperty.service.IRegisterService#register(java.lang.String
* , java.lang.String)
*/
@Override
public boolean register(Student student) {
if (isStudentExits(student.getUserName())) {
return false;
}

studentDAO.save(student);

return true;
}

}

将逻辑层托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码:

1
2
3
4
5
6
7
8
<!-- 注册业务逻辑 -->
<bean id="registerService" parent="baseTransactionProxy">
<property name="target">
<bean class="com.ilovecl.myproperty.service.impl.RegisterService">
<property name="studentDAO" ref="studentDAO" />
</bean>
</property>
</bean>

编写Struts2的Action

到这里,我们就进入了Struts2的MVC世界。

  1. 控制层:Action属于MVC中的C;
  2. 模型层:Struts1中用java bean作为模型层,也就是MVC中的M,但该方案在Struts2中被废除,模型层的内容直接放入Action;
  3. 视图层:jsp的内容即是视图层;

Action最主要的方法是execute,在用户点击注册按钮时,会执行该方法:

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
/**
*
*/
package com.ilovecl.myproperty.struts.action;

import com.ilovecl.myproperty.model.Student;
import com.ilovecl.myproperty.service.IRegisterService;
import com.opensymphony.xwork2.ActionSupport;

/**
* 用户注册功能的Action类
*
* @author 邱永臣
*
*/
@SuppressWarnings("serial")
public class StudentRegisterAction extends ActionSupport {
private int userId;
private String userName;
private String password;
private String passwordConfirm;
private long phoneNumber;
private String email;
private String sexual;

String message;

private IRegisterService iRegisterService;

/**
*
*/
public StudentRegisterAction() {
phoneNumber = 0;
email = "";
sexual = "";
}

/*
* (non-Javadoc)
*
* @see com.opensymphony.xwork2.ActionSupport#execute()
*/
@Override
public String execute() throws Exception {
this.message = "";

if (this.userName.equals("")) {
this.message += "用户名为空!\n";
return INPUT;
} else if (this.password.equals("") || this.passwordConfirm.equals("")) {
this.message += "密码为空!\n";
return INPUT;
} else if (!this.password.equals(this.passwordConfirm)) {
this.message += "两次密码不相同!\n";
return INPUT;
}

if (iRegisterService.isStudentExits(userName)) {
this.message += "账户已存在!";
return INPUT;
}
if (iRegisterService.register(new Student(userName, password,
phoneNumber, email, sexual))) {
this.message = "注册成功";
return SUCCESS;
} else {
this.message = "注册失败";
return INPUT;
}
}

/**
* @return the userId
*/
public int getUserId() {
return userId;
}

/**
* @param userId
* the userId to set
*/
public void setUserId(int userId) {
this.userId = userId;
}

/**
* @return the userName
*/
public String getUserName() {
return userName;
}

/**
* @param userName
* the userName to set
*/
public void setUserName(String userName) {
this.userName = userName;
}

/**
* @return the password
*/
public String getPassword() {
return password;
}

/**
* @param password
* the password to set
*/
public void setPassword(String password) {
this.password = password;
}

/**
* @return the passwordConfirm
*/
public String getPasswordConfirm() {
return passwordConfirm;
}

/**
* @param passwordConfirm
* the passwordConfirm to set
*/
public void setPasswordConfirm(String passwordConfirm) {
this.passwordConfirm = passwordConfirm;
}

/**
* @return the phoneNumber
*/
public long getPhoneNumber() {
return phoneNumber;
}

/**
* @param phoneNumber
* the phoneNumber to set
*/
public void setPhoneNumber(long phoneNumber) {
this.phoneNumber = phoneNumber;
}

/**
* @return the email
*/
public String getEmail() {
return email;
}

/**
* @param email
* the email to set
*/
public void setEmail(String email) {
this.email = email;
}

/**
* @return the sexual
*/
public String getSexual() {
return sexual;
}

/**
* @param sexual
* the sexual to set
*/
public void setSexual(String sexual) {
this.sexual = sexual;
}

/**
* @return the iRegisterService
*/
public IRegisterService getiRegisterService() {
return iRegisterService;
}

/**
* @param iRegisterService
* the iRegisterService to set
*/
public void setiRegisterService(IRegisterService iRegisterService) {
this.iRegisterService = iRegisterService;
}

/**
* @return the message
*/
public String getMessage() {
return message;
}

/**
* @param message
* the message to set
*/
public void setMessage(String message) {
this.message = message;
}

}

将Action托管给Spring

在WebRoot/WEB-INF/applicationContext.xml中增加下面的代码代码:

1
2
3
4
5
<!-- 学生注册界面的Action -->
<bean id="studentRegisterAction"
class="com.ilovecl.myproperty.struts.action.StudentRegisterAction">
<property name="iRegisterService" ref="registerService" />
</bean>

让Struts2找到从Spring那里找到Action

由于Spring管理着Action,Struts2需要Action的时候,只能找Spring要。

在struts.xml中增加下面的代码代码:

1
2
3
4
<action name="register" class="studentRegisterAction">
<result name="success">/register.jsp</result>
<result name="input">/register.jsp</result>
</action>

编写视图层页面(jsp)

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
<%@ page contentType="text/html;charset=utf-8"%>
<%@ taglib prefix="s" uri="/struts-tags"%>

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>

<title>用户注册</title>

</head>

<body><br><br><br><br>
<div align="center">
${requestScope.message}
<s:form action="register" method="POST">
<s:textfield name="userName" label="user name" />
<s:password name="password" size="21" label="password" />
<s:password name="passwordConfirm" size="21" label="passwordConfirm" />
<s:textfield name="phoneNumber" label="phoneNumber" />
<s:textfield name="email" label="email" />
<s:textfield name="sexual" label="sexual" />
<s:submit value="OK" />
</s:form>
</div>
</body>
</html>

其它

上面是就是一个完整的SSH2实现的注册模块,在运行之前必须先建立数据库,数据库的信息和建表命令都在上面。

JAVA值传递

Posted on 2016-05-15
Symbols count in article: 2.4k | Reading time ≈ 4 mins.

问题的来源

写项目时,有一个方法需要返回两种类型的对象,所以我将两个空白的对象作为参数传给方法,在方法里修改。修改时,我没有一条条地填上空白对象的属性,而是贪图方便,将一个新对象赋值给空白对象,结果原来的那个空白对象仍旧是空白的。

问题详情

java不同于C++,在参数传递中只有值传递,没有引用传递。在下面的方法声明里,repairOrder是一个RepairOrder对象的引用,student是一个Student对象的引用:

1
2
3
4
5
6
7
8
9
10
public boolean getDetailOfRepairOrder(int repairOrderId,
RepairOrder repairOrder, Student student) {
repairOrder.setName("test");
student.setPhone(18819473231);

RepairOrder newR = new RepairOrder();
newR.setName("newR test");

repairOrder = newR;
}

我将一个r和一个s传给上面的函数:

1
2
3
RepairOrder r = new RepairOrder();
Student s = new Student();
getDetailOfRepairOrder(3234234, r, s)

程序的结果是,r的name属性是test而不是newR test,为什么?

Read more »

1…567

邱永臣

一个吃瓜群众,有时跑龙套,有时码字.

100 posts
13 categories
33 tags
GitHub E-Mail
© 2015 – 2021 邱永臣 | 480k | 13:20
备案号 粤ICP备19015297号
|