Website Logo. Upload to /source/logo.png ; disable in /source/_includes/logo.html

舞乐 VOLER

舞动我人生

Spring学习之从getBean接着说

Feb 22, 2017

上一篇留了一个TODO,这里从DefaultListableBeanFactory#preInstantiateSingletons开始继续跟踪源码。

loadBeanDefinitions结束之后,DefaultListableBeanFactory#beanDefinitionNames中保存了beanName。这里通过预调用AbstractBeanFactory#getBean(String)实例化所有的bean。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Create bean instance.
if (mbd.isSingleton()) {
  sharedInstance = getSingleton(beanName, new ObjectFactory<Object>() {
      @Override
      public Object getObject() throws BeansException {
          try {
              return createBean(beanName, mbd, args);
          }
          catch (BeansException ex) {
              destroySingleton(beanName);
              throw ex;
          }
      }
  });
  bean = getObjectForBeanInstance(sharedInstance, name, beanName, mbd);
}

继续跟踪源码来到AbstractAutowireCapableBeanFactory#createBean(String, RootBeanDefinition, Object[])中的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 try {
      // Give BeanPostProcessors a chance to return a proxy instead of the target bean instance.
      Object bean = resolveBeforeInstantiation(beanName, mbdToUse);
      if (bean != null) {
          return bean;
      }
  }
  catch (Throwable ex) {
      throw new BeanCreationException(mbdToUse.getResourceDescription(), beanName,
              "BeanPostProcessor before instantiation of bean failed", ex);
  }

  Object beanInstance = doCreateBean(beanName, mbdToUse, args);
  if (logger.isDebugEnabled()) {
      logger.debug("Finished creating instance of bean '" + beanName + "'");
  }
  return beanInstance;
}

上一篇提到注册BeanPostProcessor,这里的resolveBeforeInstantiation即检查注册的BeanPostProcessor是否实现了InstantiationAwareBeanPostProcessor接口,如果是,这里会调用实现的postProcessBeforeInstantiation方法。

接着AbstractAutowireCapableBeanFactory#createBeanInstance实例化bean并包装为BeanWrapper;AbstractAutowireCapableBeanFactory#populateBean会检查注册的BeanPostProcessor是否实现了InstantiationAwareBeanPostProcessor接口,如果是,这里会调用实现的postProcessAfterInstantiation、postProcessPropertyValues方法。AbstractAutowireCapableBeanFactory#applyPropertyValues会尝试使用BeanWrapper注册的PropertyEditor修改property。

后面的过程和BeanFactory javadoc中的描述一致,会依次调用

  1. postProcessBeforeInitialization methods of BeanPostProcessors
  2. InitializingBean’s afterPropertiesSet
  3. a custom init-method definition
  4. postProcessAfterInitialization methods of BeanPostProcessors

createBean占了大半篇幅,这里重新回到开头,createBean方法调用结束后得到sharedInstance,接着检查sharedInstance是否为FactoryBean实例,如果是,会调用FactoryBean#getObject方法,方法的返回值作为最后的返回结果。

Spring学习之AOP

Feb 22, 2017

AnnotationAwareAspectJAutoProxyCreator帮助我们基于注解实现AOP,它实现了BeanPostProcessor接口,那就从其实现的postProcessAfterInitialization方法(AbstractAutoProxyCreator#postProcessAfterInitialization)跟踪AOP是如何实现的。

跟踪源码来到AbstractAutoProxyCreator#wrapIfNecessary中的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
...
// Create proxy if we have advice.
Object[] specificInterceptors = getAdvicesAndAdvisorsForBean(bean.getClass(), beanName, null);
if (specificInterceptors != DO_NOT_PROXY) {
  this.advisedBeans.put(cacheKey, Boolean.TRUE);
  Object proxy = createProxy(
          bean.getClass(), beanName, specificInterceptors, new SingletonTargetSource(bean));
  this.proxyTypes.put(cacheKey, proxy.getClass());
  return proxy;
}

this.advisedBeans.put(cacheKey, Boolean.FALSE);
return bean;
}

现在看一下具体每一步做了什么。

  • getAdvicesAndAdvisorsForBean

    • findCandidateAdvisors

首先使用BeanFactoryUtils#beanNamesForTypeIncludingAncestors(ListableBeanFactory, Class, boolean, boolean)获取所有的Advisor并使用BeanFactory#getBean(String, Class)实例化。

接着遍历所有的Object,通过AbstractAspectJAdvisorFactory#isAspect获取具有@Aspect注解的bean;再遍历bean,获取bean中不具有@Pointcut注解的方法,先按具有@Around@Before@After@AfterReturning@AfterThrowing排序,再按方法名排序;获取注解中表达式对应的AspectJExpressionPointcut;最后得到该bean相关的InstantiationModelAwarePointcutAdvisorImpl列表。使用BeanFactoryAspectJAdvisorsBuilder#advisorsCache保存beanName与其Advisor列表的对应关系。

    • findAdvisorsThatCanApply

上一步是获取所有切面,这一步是获取应用于当前bean的切面(AopUtils#canApply(Pointcut, Class, boolean))。

TODO

org.aspectj.util.PartialOrder#sort

  • createProxy

DefaultAdvisorAdapterRegistry#wrap将获取的切面都包装为Advisor实例,实例化ProxyFactory,由ProxyFactory#getProxy(ClassLoader)继续跟踪代码到JdkDynamicAopProxy#getProxy(ClassLoader),

1
return Proxy.newProxyInstance(classLoader, proxiedInterfaces, this);

返回代理之前会将Advised接口添加到proxiedInterfaces末尾。

JdkDynamicAopProxy实现了InvocationHandler,那下面就看一下它是如何实现invoke方法的。

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
// Get the interception chain for this method.
List<Object> chain = this.advised.getInterceptorsAndDynamicInterceptionAdvice(method, targetClass);

// Check whether we have any advice. If we don't, we can fallback on direct
// reflective invocation of the target, and avoid creating a MethodInvocation.
if (chain.isEmpty()) {
  // We can skip creating a MethodInvocation: just invoke the target directly
  // Note that the final invoker must be an InvokerInterceptor so we know it does
  // nothing but a reflective operation on the target, and no hot swapping or fancy proxying.
  Object[] argsToUse = AopProxyUtils.adaptArgumentsIfNecessary(method, args);
  retVal = AopUtils.invokeJoinpointUsingReflection(target, method, argsToUse);
}
else {
  // We need to create a method invocation...
  invocation = new ReflectiveMethodInvocation(proxy, target, method, args, targetClass, chain);
  // Proceed to the joinpoint through the interceptor chain.
  retVal = invocation.proceed();
}

// Massage return value if necessary.
Class<?> returnType = method.getReturnType();
if (retVal != null && retVal == target && returnType.isInstance(proxy) &&
      !RawTargetAccess.class.isAssignableFrom(method.getDeclaringClass())) {
  // Special case: it returned "this" and the return type of the method
  // is type-compatible. Note that we can't help if the target sets
  // a reference to itself in another returned object.
  retVal = proxy;
}
else if (retVal == null && returnType != Void.TYPE && returnType.isPrimitive()) {
  throw new AopInvocationException(
          "Null return value from advice does not match primitive return type for: " + method);
}
return retVal;

Spring学习之从refresh说起

Feb 22, 2017

这里我们以ClassPathXmlApplicationContext为例,跟踪Spring的启动过程,其实主要是跟踪AbstractApplicationContext.refresh。

1

跟踪源码来到AbstractApplicationContext#prepareRefresh中的

1
2
3
// Validate that all properties marked as required are resolvable
// see ConfigurablePropertyResolver#setRequiredProperties
getEnvironment().validateRequiredProperties();

那我们就先来看一下Environment相关的内容。

AbstractApplicationContext内置了environment变量,getEnvironment通过createEnvironment方法,将environment实例化为StandardEnvironment。下面的代码算是一个概括性描述,

1
private ConfigurableEnvironment environment = new StandardEnvironment();

StandardEnvironment重写了customizePropertySources方法,目的是在实例化时将System.getProperties()获取的系统属性以及System.getenv()获取的系统环境变量添加到propertySources中。propertySources是基于CopyOnWriteArrayList<PropertySource<?>>实现的MutablePropertySources实例。

除了重写customizePropertySources方法,其他的方法仍由AbstractEnvironment来实现,propertySources即内置于AbstractEnvironment。从上图可以看出AbstractEnvironment同时实现了EnvironmentConfigurablePropertyResolver接口,AbstractEnvironment基于LinkedHashSet实现了Environment(profile)相关的方法,而ConfigurablePropertyResolver相关的方法则由其内置的一个PropertySourcesPropertyResolver实例来实现。比如,

1
2
3
4
@Override
public void validateRequiredProperties() throws MissingRequiredPropertiesException {
  this.propertyResolver.validateRequiredProperties();
}
2

接着来到AbstractApplicationContext#obtainFreshBeanFactory中的

1
refreshBeanFactory();

上述方法由AbstractRefreshableApplicationContext#refreshBeanFactory实现,销毁相关的bean(清理bean相关的对象),关闭BeanFactory,重新实例化BeanFactory。

1
DefaultListableBeanFactory beanFactory = new DefaultListableBeanFactory(null);

beanFactory通过内置的serializableFactories保存serializationId与其自身弱引用的对应关系。在下面提到的loadBeanDefinitions结束之后,将beanFactory赋给AbstractApplicationContext内置的beanFactory

loadBeanDefinitions方法被多次重载,最终到AbstractBeanDefinitionReader#loadBeanDefinitions(String, Set)可以分为两部分,第一部分是获取资源文件,第二部分是从资源文件中获取BeanDefinition。

  • getResources

beanFactory自身作为XmlBeanDefinitionReader内置的resourceLoader,得到XmlBeanDefinitionReader实例,同时将其environment赋值给XmlBeanDefinitionReader内置的environment

reader将getResources的任务交给其实例化时的resourceLoader,即beanFactory;beanFactory又将getResources的任务交给其内置的resourcePatternResolverPathMatchingResourcePatternResolver实例)。

  • loadBeanDefinitions

继续跟踪源码来到DefaultBeanDefinitionDocumentReader#doRegisterBeanDefinitions中的

1
2
3
4
5
6
7
8
9
10
if (this.delegate.isDefaultNamespace(root)) {
  String profileSpec = root.getAttribute(PROFILE_ATTRIBUTE);
  if (StringUtils.hasText(profileSpec)) {
      String[] specifiedProfiles = StringUtils.tokenizeToStringArray(
          profileSpec, BeanDefinitionParserDelegate.MULTI_VALUE_ATTRIBUTE_DELIMITERS);
      if (!getReaderContext().getEnvironment().acceptsProfiles(specifiedProfiles)) {
          return;
      }
  }
}

这里如果元素配置了profile属性,则会通过前面的environment检查配置的profile是否符合,如果不符合则跳过当前资源文件。

接着来到DefaultBeanDefinitionDocumentReader#processBeanDefinition中的

1
2
3
4
BeanDefinitionHolder bdHolder = delegate.parseBeanDefinitionElement(ele);
...
  // Register the final decorated instance.
  BeanDefinitionReaderUtils.registerBeanDefinition(bdHolder, getReaderContext().getRegistry());

BeanDefinitionReaderUtils#createBeanDefinition返回GenericBeanDefinition实例,设置其相应的属性,包装成BeanDefinitionHolder实例。

这里getRegistry返回的是实例化XmlBeanDefinitionReader时传入的beanFactory,所以回到DefaultListableBeanFactory#registerBeanDefinition。

关于设置GenericBeanDefinition实例的属性,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public void setBeanClassName(String beanClassName) {
  this.beanClass = beanClassName;
}

@Override
public String getBeanClassName() {
  Object beanClassObject = this.beanClass;
  if (beanClassObject instanceof Class) {
      return ((Class<?>) beanClassObject).getName();
  }
  else {
      return (String) beanClassObject;
  }
}
3

接着跟踪源码来到AbstractApplicationContext#prepareBeanFactory中的,

1
2
// Configure the bean factory with context callbacks.
beanFactory.addBeanPostProcessor(new ApplicationContextAwareProcessor(this));

看一下ApplicationContextAwareProcessor重写的postProcessBeforeInitialization方法,该方法会调用ApplicationContextAwareProcessor#invokeAwareInterfaces

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void invokeAwareInterfaces(Object bean) {
  if (bean instanceof Aware) {
      if (bean instanceof EnvironmentAware) {
          ((EnvironmentAware) bean).setEnvironment(this.applicationContext.getEnvironment());
      }
      if (bean instanceof EmbeddedValueResolverAware) {
          ((EmbeddedValueResolverAware) bean).setEmbeddedValueResolver(
                  new EmbeddedValueResolver(this.applicationContext.getBeanFactory()));
      }
      if (bean instanceof ResourceLoaderAware) {
          ((ResourceLoaderAware) bean).setResourceLoader(this.applicationContext);
      }
      if (bean instanceof ApplicationEventPublisherAware) {
          ((ApplicationEventPublisherAware) bean).setApplicationEventPublisher(this.applicationContext);
      }
      if (bean instanceof MessageSourceAware) {
          ((MessageSourceAware) bean).setMessageSource(this.applicationContext);
      }
      if (bean instanceof ApplicationContextAware) {
          ((ApplicationContextAware) bean).setApplicationContext(this.applicationContext);
      }
  }
}

如果bean实现了以下接口,包括EnvironmentAwareEmbeddedValueResolverAwareResourceLoaderAwareApplicationEventPublisherAwareMessageSourceAwareApplicationContextAware,则bean在初始化之前,相应的实现方法将被调用。

4

跟踪源码来到AbstractApplicationContext#invokeBeanFactoryPostProcessors,获取beanFactory中已经注册的BeanFactoryPostProcessor,调用其中的postProcessBeanFactory方法。调用之前会判断处理器是否实现了BeanDefinitionRegistryPostProcessor接口,如果实现了,则先调用其中的postProcessBeanDefinitionRegistry方法,不再调用postProcessBeanFactory方法。

1
2
String[] postProcessorNames =
  beanFactory.getBeanNamesForType(BeanDefinitionRegistryPostProcessor.class, true, false);

再使用DefaultListableBeanFactory#getBeanNamesForType获取未注册的BeanFactoryPostProcessor,重复上述过程。

5

接着跟踪源码来到AbstractApplicationContext#registerBeanPostProcessors,注册尚未注册的BeanPostProcessor,最后会重新注册实现了MergedBeanDefinitionPostProcessor接口的处理器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// First, register the BeanPostProcessors that implement PriorityOrdered.
sortPostProcessors(beanFactory, priorityOrderedPostProcessors);
registerBeanPostProcessors(beanFactory, priorityOrderedPostProcessors);

// Next, register the BeanPostProcessors that implement Ordered.
...
sortPostProcessors(beanFactory, orderedPostProcessors);
registerBeanPostProcessors(beanFactory, orderedPostProcessors);

// Now, register all regular BeanPostProcessors.
...
registerBeanPostProcessors(beanFactory, nonOrderedPostProcessors);

// Finally, re-register all internal BeanPostProcessors.
sortPostProcessors(beanFactory, internalPostProcessors);
registerBeanPostProcessors(beanFactory, internalPostProcessors);

6

接着初始化MessageSourceApplicationEventMulticaster,注册监听者并广播早期的ApplicationEvents

TODO

  • DefaultListableBeanFactory#preInstantiateSingletons
  • AbstractBeanFactory#doGetBean

最后初始化LifecycleProcessor

7

Spring容器-ApplicationContext的启动过程

反序列化时的readResolve

Jan 23, 2017

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
package org.springframework.aop;

import java.io.Serializable;

/**
 * Canonical Pointcut instance that always matches.
 *
 * @author Rod Johnson
 */
@SuppressWarnings("serial")
class TruePointcut implements Pointcut, Serializable {

  public static final TruePointcut INSTANCE = new TruePointcut();

  /**
  * Enforce Singleton pattern.
  */
  private TruePointcut() {
  }

  @Override
  public ClassFilter getClassFilter() {
      return ClassFilter.TRUE;
  }

  @Override
  public MethodMatcher getMethodMatcher() {
      return MethodMatcher.TRUE;
  }

  /**
  * Required to support serialization. Replaces with canonical
  * instance on deserialization, protecting Singleton pattern.
  * Alternative to overriding {@code equals()}.
  */
  private Object readResolve() {
      return INSTANCE;
  }

  @Override
  public String toString() {
      return "Pointcut.TRUE";
  }

}

这里直接给出TruePointcut的源码,可以看出其使用了单例模式。但是这里定义了一个private Object readResolve(),javadoc中还写着在反序列化时保护单例模式,那它是如何起到保护作用的呢?

联想到我们可以在序列化、反序列化时自定义writeObjectreadObject方法,那readResolve是不是与其类似呢?

1
2
3
4
5
private void writeObject(java.io.ObjectOutputStream s)
  throws IOException;

private void readObject(java.io.ObjectInputStream s)
  throws IOException, ClassNotFoundException;

ObjectInputStream#readOrdinaryObject中的部分源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 ...
    if (desc.isExternalizable()) {
        readExternalData((Externalizable) obj, desc);
    } else {
        readSerialData(obj, desc);
    }

    handles.finish(passHandle);

    if (obj != null &&
        handles.lookupException(passHandle) == null &&
        desc.hasReadResolveMethod())
    {
        Object rep = desc.invokeReadResolve(obj);
        if (unshared && rep.getClass().isArray()) {
            rep = cloneArray(rep);
        }
        if (rep != obj) {
            handles.setObject(passHandle, obj = rep);
        }
    }

    return obj;
}

从源码可以看出,如果自定义了readResolve方法,反序列化的最终结果将取决于该方法的返回值。所以这里可以在反序列时保护单例模式

关于IntegerCache

Jan 10, 2017

很久没有写文章了,今天以一段代码重新开始,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Integer a = 127;
Integer b = 127;
int c = 127;
System.out.println(a == b);
System.out.println(a == c);

a = 128;
b = 128;
c = 128;
System.out.println(a == b);
System.out.println(a == c);

a = new Integer(127);
b = new Integer(127);
System.out.println(a == b);

这里还给出了代码截图,可以看到这段代码在IDE中有多处warning提示,包括

Condition ‘a == c’ is always ‘true’
Unnecessary boxing ‘new Integer(127)’
Number objects are compared using ‘==’, not ‘equals()’

实际编码时应该按照提示修改warning。这里直接给出执行结果

true
true
false
true
false

了解自动拆箱的知识后,a == c的结果很好理解,包装类型a与原始类型c进行比较时,自动拆箱,相当于127 == 127以及128 == 128,所以c相关的结果都是true。再看一下最后一个a == b,了解equals与==的区别后,结果是false也好理解,这里还提示我们应该使用equals来比较包装类型a和b。本文主要关注前两个a == b,127时结果是true,128时结果是false。

了解自动装箱的知识后,明白这里Integer a = 127等价于Integer a = Integer.valueOf(127)。那现在就看一下valueOf这个方法做了什么。

1
2
3
4
5
6
public static Integer valueOf(int i) {
    assert IntegerCache.high >= 127;
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

原来valueOfIntegerCache这个类相关,那再看一下IntegerCache这个类做了什么。

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
private static class IntegerCache {
    static final int low = -128;
    static final int high;
    static final Integer cache[];

    static {
        // high value may be configured by property
        int h = 127;
        String integerCacheHighPropValue =
            sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
        if (integerCacheHighPropValue != null) {
            int i = parseInt(integerCacheHighPropValue);
            i = Math.max(i, 127);
            // Maximum array size is Integer.MAX_VALUE
            h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
        }
        high = h;

        cache = new Integer[(high - low) + 1];
        int j = low;
        for(int k = 0; k < cache.length; k++)
            cache[k] = new Integer(j++);
    }

    private IntegerCache() {}
}

IntegerCache中定义了一个Integer数组,初始化时,这个数组预先保存了[-128, high]之间的Integer实例。valueOf方法在自动装箱时会判断需要装箱的数是否在这个区间内,如果在则返回预先保存的实例,不在则新实例化。默认的区间范围是[-128, 127],第一次装箱127时,返回的是预先保存的同一个实例,所以结果为true;第二次装箱128时,返回的是新实例化的对象,所以结果为false。

除了Integer内建了IntegerCache,Byte、Short、Long也内建了相应的类。

Could Not Get the Value for Parameter compilerId for Plugin Execution

Apr 16, 2016

最近Eclipse下的很多Maven工程报错,导入其他的Maven工程时也同样报错,报错的日志类似如下,

CoreException: Could not get the value for parameter compilerId for plugin execution default-compile: PluginResolutionException: Plugin org.apache.maven.plugins:maven-compiler-plugin:3.1 or one of its dependencies could not be resolved: The following artifacts could not be resolved: org.apache.maven:maven-core:jar:2.0.9, org.apache.maven:maven-settings:jar:2.0.9, org.apache.maven:maven-plugin-parameter-documenter:jar:2.0.9, org.apache.maven:maven-profile:jar:2.0.9, org.apache.maven:maven-model:jar:2.0.9, org.apache.maven:maven-repository-metadata:jar:2.0.9, org.apache.maven:maven-error-diagnostics:jar:2.0.9, org.apache.maven:maven-project:jar:2.0.9, org.apache.maven:maven-plugin-registry:jar:2.0.9, org.apache.maven:maven-plugin-descriptor:jar:2.0.9, org.apache.maven:maven-artifact-manager:jar:2.0.9, org.apache.maven:maven-monitor:jar:2.0.9, org.apache.maven:maven-toolchain:jar:1.0, org.apache.maven.shared:maven-shared-utils:jar:0.1, com.google.code.findbugs:jsr305:jar:2.0.1, org.apache.maven.shared:maven-shared-incremental:jar:1.1, org.codehaus.plexus:plexus-component-annotations:jar:1.5.5, org.codehaus.plexus:plexus-compiler-api:jar:2.2, org.codehaus.plexus:plexus-compiler-manager:jar:2.2, org.codehaus.plexus:plexus-compiler-javac:jar:2.2, org.codehaus.plexus:plexus-container-default:jar:1.5.5, org.codehaus.plexus:plexus-classworlds:jar:2.2.2, org.apache.xbean:xbean-reflect:jar:3.4, log4j:log4j:jar:1.2.12, commons-logging:commons-logging-api:jar:1.1, com.google.collections:google-collections:jar:1.0: Failure to transfer org.apache.maven:maven-core:jar:2.0.9 from https://repo.maven.apache.org/maven2 was cached in the local repository, resolution will not be reattempted until the update interval of central has elapsed or updates are forced. Original error: Could not transfer artifact org.apache.maven:maven-core:jar:2.0.9 from/to central (https://repo.maven.apache.org/maven2): The operation was cancelled.

开始认为是org.apache.maven.plugins:maven-compiler-plugin:3.1插件下载失败,检查本地仓库时,发现该插件已下载成功。今天参考 CoreException: Could not get the value for parameter compilerId for plugin execution default-compile 继续向下看日志,关键的错误日志应该是,

Failure to transfer org.apache.maven:maven-core:jar:2.0.9 from https://repo.maven.apache.org/maven2 was cached in the local repository, resolution will not be reattempted until the update interval of central has elapsed or updates are forced.

确认本地仓库中的org.apache.maven:maven-core:jar:2.0.9已下载成功,仍然报错的原因是,

resolution will not be reattempted until the update interval of central has elapsed or updates are forced.

参考 Error in pom.xml Maven build,在Eclipse中使用Alt+F5快捷键,在弹出的Update Maven Project对话框中选择报错的Maven工程,勾选下图中的Force Update of Snapshots/Releases,更新结束后,问题解决。

alt + F5

利用后缀数组解决问题

Apr 03, 2016

在介绍后缀数组之前,以字符串"aabaaaab"为例建立两个字符串数组,

1
2
3
4
5
6
String[] before = new String[s.length()];
for(int i = 0; i < before.length; i++) {
  before[i] = s.substring(i);
}
java.util.Arrays.sort(before);
String[] after = before;

before数组的内容为,

1
{ "aabaaaab", "abaaaab", "baaaab", "aaaab", "aaab", "aab", "ab", "b" }

对before数组元素按字典序进行排序,得到after数组,

1
{ "aaaab", "aaab", "aab", "aabaaaab", "ab", "abaaaab", "b", "baaaab" }

后缀数组suffix的定义为,after[i]=before[suffix[i]-1],即排第几的元素是什么?

1
{ 4, 5, 6, 1, 7, 2, 8, 3 }

名次数组rank的定义为,before[i]=after[rank[i]-1],即该元素排第几?

1
{ 4, 6, 8, 1, 2, 3, 5, 7 }

height数组保存after数组中相邻元素之间的最长前缀,

1
2
3
4
5
6
7
8
9
10
11
String[] height = new String[after.length];
height[0] = "";
for(int i = 1; i < height.length; i++) {
  int x = 0, y = 0;
    for(; x < after[i - 1].length() && y < after[i].length(); x++, y++) {
      if(after[i - 1].charAt(x) != after[i].charAt(y)) {
          break;
        }
    }
  height[i] = after[i - 1].substring(0, x);
}
1
{ "", "aaa", "aa", "aab", "a", "ab", "", "b" }
可重叠最长重复子串

即为height数组中length最大的元素,"aaa""aab"

最长回文子串

将原字符串翻转后拼接到原字符串末尾,中间用特殊字符(如$)隔开,得到新的字符串"aabaaaab$baaaabaa",新字符串的height数组为,

1
{ "", "", "a", "aa", "aaaab", "aaa", "aaab", "aa", "aab", "aabaa", "a", "ab", "abaa", "", "b", "baa", "baaaab" }

最长回文子串即为height数组中length最大的元素,"baaaab"

最近公共祖先问题

Mar 28, 2016

从git merge说起

接着 使用Git协同工作 中的内容,使用伪代码描述git merge的原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
找到目标分支current和被合并分支merge的共同祖先分支ancestor;
// 在fix_bug分支上执行git merge master
// master为目标分支,fix_bug为被合并分支
if(ancestor == merge) {
  return;
} else if(ancestor == current) {
  fast forward merge,分支current指向merge
} else {
  确定ancestor与merge的差异
  try {
      将差异合并到current
    } catch(合并出现矛盾) {
      添加矛盾标记,通知用户解决矛盾
        return;
    }
    根据current、merge创建新的子分支
    分支current指向新的子分支
}

Git的分支结构为树形结构,这里找到两个分支的共同祖先分支,即求树中两个节点的最近公共祖先

如果每个分支可以确定其父分支,即树中节点具有指向其父亲的parent指针,那问题可以转化为求两个链表的公共节点。两个节点分别使用parent指针遍历到根节点root,遍历步数之差即两节点到公共节点的步数之差,由步数较大的节点先遍历步数之差对应的步数,接着两节点同时使用parent指针遍历,当parent指针的指向一致时,其指向即所求的公共节点。可以进一步参考 两链表的第一个公共结点

如果树为平衡二叉树,根据BST的性质,从根节点root开始遍历,如果当前节点的值同时大于两节点的值,说明两节点都位于当前节点的左子树,接下来向左子树遍历;如果当前节点的值同时小于两节点的值,说明两节点都位于当前节点的右子树,接下来向右子树遍历;如果当前节点的值位于两节点的值之间,那当前节点即所求的公共节点。

下面介绍使用Tarjan离线算法解决上述问题,Tarjan算法基于深度遍历和并查集,先介绍并查集相关的内容。

并查集

并查集详解 (转) 非常生动地介绍了并查集相关的内容,这里给出并查集的Java实现。

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
public class UnionFindSet {

  private int[] set;
  private static final int INIT_SET_SIZE = 8;
  /** 参数超出并查集下标范围,返回ERROR_INDEX */
  private static final int ERROR_INDEX = -1;

  public UnionFindSet() {
      this(INIT_SET_SIZE);
  }

  public UnionFindSet(int size) {
      set = new int[size];
      for (int i = 0; i < set.length; i++) {
          set[i] = i;
      }
  }

  /**
  * 等价于find(x, true)
  * 
  * @param x
  * @return
  */
  public int find(int x) {
      if (outOfLength(x)) {
          return ERROR_INDEX;
      }

      if (set[x] != x) {
          set[x] = find(set[x]);
      }
      return set[x];
  }

  /**
  * 
  * @param x
  * @param compress
  *            是否压缩路径
  * @return x超出并查集下标范围,返回ERROR_INDEX;否则返回x的根元素
  */
  public int find(int x, boolean compress) {
      if (outOfLength(x)) {
          return ERROR_INDEX;
      }
      if (compress) {
          return find(x);
      }

      int temp = x;
      while (set[temp] != temp) {
          temp = set[temp];
      }
      return temp;
  }

  /**
  * 
  * @param x
  * @param y
  * @return x、y的根元素是否相等
  */
  public boolean query(int x, int y) {
      if (outOfLength(x) || outOfLength(y)) {
          return false;
      }
      return find(x) == find(y);
  }

  /**
  * 将x、y合并到同一根元素下
  * 
  * @param x
  * @param y
  */
  public void join(int x, int y) {
      int prex = find(x);
      int prey = find(y);
      if (prex != ERROR_INDEX && prey != ERROR_INDEX && prex != prey) {
          set[prex] = prey;
      }
  }

  private boolean outOfLength(int index) {
      return index < 0 || index >= set.length;
  }

}
Tanjar离线算法

理解并查集之后,Tanjar算法即将并查集与深度遍历有效结合,伪代码描述原理为

1
2
3
4
5
6
7
8
9
Tarjan(u) {
  begin
      设置u号节点的祖先为u
        深度遍历u的子树
        访问每一条与u相关的询问u和v
          -若v已经被访问过则输出v当前的祖先t
        标记u为已被访问将所有u的子节点包括u本身的祖先改为u的父节点
    end
}

具体的Java实现

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
/**
 *
 * @param node
 * @param queryList
 *            LCA查询条件列表,Query类的u、v属性为查询条件,即已知的两节点;ancestor属性保存查询结果,即公共节点
 */
public void tarjan(TreeNode node, ArrayList<Query> queryList) {
  node.ancestor = node;// 初始标记node的祖先为自己
  for (TreeNode child : node.children) {
      tarjan(child, queryList);// 深度遍历
      join(child, node);// 将子节点的祖先修改为node
  }

  node.searched = true;// 标记node已被访问
  // 遍历查询条件,如果查询条件与node相关且两节点已被访问,基于并查集查找公共节点
  for (Query query : queryList) {
      if (query.u == node) {
          if (query.v.searched) {
              query.ancestor = find(query.v);
          }
      } else if (query.v == node) {
          if (query.u.searched) {
              query.ancestor = find(query.u);
          }
      }
  }
}

对ConcurrentHashMap的解释

Feb 27, 2016

java.util.concurrent.ConcurrentHashMap整体为Segment数组,concurrentLevel为初始化参数,2sshift-1^ < concurrentLevel <= 2sshift^,Segment数组的大小ssize = 2sshift^,

1
2
3
4
5
6
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
  ++sshift;
  ssize <<= 1;
}

ssize * (c - 1) < initialCapacity <= ssize * c,每个数组元素Segment的容量cap与c的大小关系,和ssize与concurrentLevel的大小关系一致,

1
2
3
4
5
6
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
  ++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
  cap <<= 1;

初始化时,使用UNsafe.putOrderedObject将新建Segment存入数组的0下标处,

1
2
3
4
5
6
7
8
9
10
Class sc = Segment[].class;
SBASE = UNSAFE.arrayBaseOffset(sc);
ss = UNSAFE.arrayIndexScale(sc);
SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
// create segments and segments[0]
Segment<K,V> s0 =
  new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                  (HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]

使用put方法添加新的键值对时,仍然先计算key的哈希值,hash方法与HashMap中的hash方法类似,添加了再哈希步骤,其目的是为了减少哈希冲突,使元素能够均匀的分布在不同的Segment上,从而提高容器的存取效率,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int hash(Object k) {
  int h = hashSeed;

    if ((0 != h) && (k instanceof String)) {
      return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

接着根据哈希值确定数组下标,这里的segmentShiftsegmentMask是初始化时根据sshiftssize确定的,

1
2
3
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
int j = (hash >>> segmentShift) & segmentMask;

反复确认j下标处的Segment是否为空,为空则依照0下标处的Segment新建Segment,使用UNSAFE.compareAndSwapObject更新null为新建Segment,

1
2
3
4
5
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
      == null) {
  if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
      break;
}

接下来的操作之前会尝试对该Segment加锁,Segment整体为HashEntry数组,每个数组元素为HashEntry链表,继续根据哈希值确定数组下标,遍历index下标处的HashEntry链表,

1
2
3
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);

与HashMap中的比较逻辑一致,确定key是否存在,

1
2
3
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
  //...
}

如果已存在,更新其对应的value;如果未存在,根据键值对新建HashEntry对象,使用UNsafe.putOrderedObject将新建HashEntry存入数组的index下标处。使用get方法获取键对应的值时,不需要对当前Segment加锁,类似地先确定Segment数组下标,再确定HashEntry数组下标,遍历链表,比较确定key是否存在,如果存在返回对应的value;不存在返回null

文章中表述不清的地方可以进一步参考聊聊并发(四)——深入分析ConcurrentHashMap,对于UNsafe类中的方法,可以参考Java中Unsafe类详解

对Hashtable和HashMap的补充解释

Feb 26, 2016

java.util.Hashtable使用synchronized关键字实现线程安全,value不可以为空,

1
2
3
if (value == null) {
  throw new NullPointerException();
}

key也不可为空,计算key的哈希值时会调用它的hashCode方法

1
2
3
4
private int hash(Object k) {
  // hashSeed will be zero if alternative hashing is disabled.
    return hashSeed ^ k.hashCode();
}

默认情况下hashSeed为0,即不使用alternative hashing,可以设置容量达到特定阀值时开始使用alternative hashing,这时,

1
hashSeed = sun.misc.Hashing.randomHashSeed(this);

Hashtable整体为数组tab,每个数组元素为Entry链表,使用put方法添加新的键值对时,首先计算key的哈希值,根据哈希值确定数组下标,

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

接着遍历index处的Entry链表,通过下面的比较逻辑确定key是否存在,

1
2
3
if ((e.hash == hash) && e.key.equals(key)) {
  //...
}

如果已存在,更新其对应的value;如果未存在,根据键值对新建Entry对象,插入到当前Entry链表的首位。使用get方法获取键对应的值时,类似地确定数组下标,遍历链表,比较确定key是否存在,如果存在返回对应的value;不存在返回null

容量大于设定的阀值时会调用rehash方法扩容,这时会重新计算每个键值对的数组下标及位置。

java.util.HashMapHashtable类似,区别在于无synchronized关键字,HashMap中key、value可以为空,key为null的键值对保存在数组的0下标处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
  int h = hashSeed;
  if (0 != h && k instanceof String) {
      return sun.misc.Hashing.stringHash32((String) k);
  }

  h ^= k.hashCode();

  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

HashMap中确定key是否存在的比较逻辑,

1
2
3
4
if (e.hash == hash &&
  ((k = e.key) == key || (key != null && key.equals(k)))) {
  //...
}