发表于

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」。

填充每个节点的下一个右侧节点指针

题目描述：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
7
8
> c复制代码struct Node {
>   int val;
>   Node *left;
>   Node *right;
>   Node *next;
> }
> 
>

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/po…

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：层序遍历
  • 首先，如果root为空或者左右子节点都为空，则不需要处理next指针，直接返回root。
  • 否则，当二叉树不只有一个节点时，利用队列对二叉树进行层序遍历记录二叉树每一层的节点，然后按顺序处理当前层每一个节点的next指针。由于处理过程中所有的节点顺序并没有进行改变，所以最后返回root。
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
java复制代码import com.kaesar.leetcode.Node;

import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_116 {
    public static Node connect(Node root) {
        // 如果root为空或者左右节点都为空，不需要处理，直接返回root
        if (root == null) {
            return root;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        // 利用队列记录每层的节点
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            int count = nodes.size();
            Node last = nodes.poll();
            if (last.left != null) {
                nodes.add(last.left);
            }
            if (last.right != null) {
                nodes.add(last.right);
            }

            count--;
//             处理每层的节点的next指针
            while (count > 0) {
                Node curNode = nodes.poll();
                if (curNode.left != null) {
                    nodes.add(curNode.left);
                }
                if (curNode.right != null) {
                    nodes.add(curNode.right);
                }
                last.next = curNode;
                last = curNode;
                count--;
            }

        }
        return root;
    }

    public static void main(String[] args) {
        // 测试用例
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        // 处理之前
        root.print();
        connect(root);
        System.out.println();
        // 处理之后
        root.print();
    }
}

【每日寄语】 好好学习，天天向上。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

请添加图片描述
上一篇文章分析到createBean执行到了doCreateBean方法：
请添加图片描述
自定义的WelcomeController下面有一个成员变量WelcomeService被@Autowired标签标记

进入到doCreateBean方法里：

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
java复制代码protected Object doCreateBean(final String beanName, final RootBeanDefinition mbd, final @Nullable Object[] args)
      throws BeanCreationException {

   // Instantiate the bean.
   // bean实例包装类
   BeanWrapper instanceWrapper = null;
   if (mbd.isSingleton()) {
      // 从未完成创建的包装Bean缓存中清理并获取相关中的包装Bean实例，毕竟是单例的，只能存一份
      instanceWrapper = this.factoryBeanInstanceCache.remove(beanName);
   }
   if (instanceWrapper == null) {
      //创建bean的时候，这里创建bean的实例有三种方法
      // 1.工厂方法创建
      // 2.构造方法的方式注入
      // 3.无参构造方法注入
      instanceWrapper = createBeanInstance(beanName, mbd, args);
   }
   final Object bean = instanceWrapper.getWrappedInstance();
   Class<?> beanType = instanceWrapper.getWrappedClass();
   if (beanType != NullBean.class) {
      mbd.resolvedTargetType = beanType;
   }

   // Allow post-processors to modify the merged bean definition.
   // 调用BeanDefinition属性合并完成后的BeanPostProcessor后置处理器
   synchronized (mbd.postProcessingLock) {
      if (!mbd.postProcessed) {
         try {
            // 被@Autowired、@Value标记的属性在这里获取
            applyMergedBeanDefinitionPostProcessors(mbd, beanType, beanName);
         }
         catch (Throwable ex) {
            throw new BeanCreationException(mbd.getResourceDescription(), beanName,
                  "Post-processing of merged bean definition failed", ex);
         }
         mbd.postProcessed = true;
      }
   }

   // Eagerly cache singletons to be able to resolve circular references
   // even when triggered by lifecycle interfaces like BeanFactoryAware.
   boolean earlySingletonExposure = (mbd.isSingleton() && this.allowCircularReferences &&
         isSingletonCurrentlyInCreation(beanName));
   if (earlySingletonExposure) {
      if (logger.isTraceEnabled()) {
         logger.trace("Eagerly caching bean '" + beanName +
               "' to allow for resolving potential circular references");
      }
      addSingletonFactory(beanName, () -> getEarlyBeanReference(beanName, mbd, bean));
   }

   // Initialize the bean instance.
   Object exposedObject = bean;
   try {
      populateBean(beanName, mbd, instanceWrapper);
      exposedObject = initializeBean(beanName, exposedObject, mbd);
   }
   catch (Throwable ex) {
      if (ex instanceof BeanCreationException && beanName.equals(((BeanCreationException) ex).getBeanName())) {
         throw (BeanCreationException) ex;
      }
      else {
         throw new BeanCreationException(
               mbd.getResourceDescription(), beanName, "Initialization of bean failed", ex);
      }
   }

   if (earlySingletonExposure) {
      Object earlySingletonReference = getSingleton(beanName, false);
      if (earlySingletonReference != null) {
         if (exposedObject == bean) {
            exposedObject = earlySingletonReference;
         }
         else if (!this.allowRawInjectionDespiteWrapping && hasDependentBean(beanName)) {
            String[] dependentBeans = getDependentBeans(beanName);
            Set<String> actualDependentBeans = new LinkedHashSet<>(dependentBeans.length);
            for (String dependentBean : dependentBeans) {
               if (!removeSingletonIfCreatedForTypeCheckOnly(dependentBean)) {
                  actualDependentBeans.add(dependentBean);
               }
            }
            if (!actualDependentBeans.isEmpty()) {
               throw new BeanCurrentlyInCreationException(beanName,
                     "Bean with name '" + beanName + "' has been injected into other beans [" +
                     StringUtils.collectionToCommaDelimitedString(actualDependentBeans) +
                     "] in its raw version as part of a circular reference, but has eventually been " +
                     "wrapped. This means that said other beans do not use the final version of the " +
                     "bean. This is often the result of over-eager type matching - consider using " +
                     "'getBeanNamesOfType' with the 'allowEagerInit' flag turned off, for example.");
            }
         }
      }
   }

   // Register bean as disposable.
   try {
      registerDisposableBeanIfNecessary(beanName, bean, mbd);
   }
   catch (BeanDefinitionValidationException ex) {
      throw new BeanCreationException(
            mbd.getResourceDescription(), beanName, "Invalid destruction signature", ex);
   }

   return exposedObject;
}

首先定义了一个包装类BeanWrapper，
请添加图片描述
该接口是spring提供的用于操作bean中属性的工具，使用它可以直接修改bean里面的属性，
请添加图片描述
BeanWrapperImpl是AbstractNestablePropertyAccessor的子类，BeanWrapper的实现类，通过父类使得其具有处理属性的能力。

回到doCreateBean，接下来判断BeanDefinition是否是单例，如果是的话尝试从缓存中获取FactoryBean实例，如果获取不到就会执行

1
java复制代码instanceWrapper = createBeanInstance(beanName, mbd, args);

进入到createBeanInstance里：

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
java复制代码protected BeanWrapper createBeanInstance(String beanName, RootBeanDefinition mbd, @Nullable Object[] args) {
   // Make sure bean class is actually resolved at this point.
   Class<?> beanClass = resolveBeanClass(mbd, beanName);
   // 检查是否有权通过反射创建private的Class
   if (beanClass != null && !Modifier.isPublic(beanClass.getModifiers()) && !mbd.isNonPublicAccessAllowed()) {
      throw new BeanCreationException(mbd.getResourceDescription(), beanName,
            "Bean class isn't public, and non-public access not allowed: " + beanClass.getName());
   }
   // 使用工厂创建实例
   Supplier<?> instanceSupplier = mbd.getInstanceSupplier();
   if (instanceSupplier != null) {
      return obtainFromSupplier(instanceSupplier, beanName);
   }

   // 如果工厂方法不为空，则使用工厂方法初始化策略
   if (mbd.getFactoryMethodName() != null) {
      return instantiateUsingFactoryMethod(beanName, mbd, args);
   }

   // Shortcut when re-creating the same bean...
   boolean resolved = false;
   boolean autowireNecessary = false;
   if (args == null) {
      synchronized (mbd.constructorArgumentLock) {
         // 如果已缓存的解析的构造函数或者工厂方法不为空，则可以利用构造函数解析
         // 因为需要根据参数确认底使用哪个构造函数
         if (mbd.resolvedConstructorOrFactoryMethod != null) {
            resolved = true;
            autowireNecessary = mbd.constructorArgumentsResolved;
         }
      }
   }
   if (resolved) {
      // 自动注入，调用构造函数自动注入
      if (autowireNecessary) {
         return autowireConstructor(beanName, mbd, null, null);
      }
      else {
         // 使用默认构造函数构造
         return instantiateBean(beanName, mbd);
      }
   }

   // Candidate constructors for autowiring?
   // 使用带参的构造函数进行装配
   Constructor<?>[] ctors = determineConstructorsFromBeanPostProcessors(beanClass, beanName);
   if (ctors != null || mbd.getResolvedAutowireMode() == AUTOWIRE_CONSTRUCTOR ||
         mbd.hasConstructorArgumentValues() || !ObjectUtils.isEmpty(args)) {
      return autowireConstructor(beanName, mbd, ctors, args);
   }

   // Preferred constructors for default construction?
   ctors = mbd.getPreferredConstructors();
   if (ctors != null) {
      return autowireConstructor(beanName, mbd, ctors, null);
   }

   // No special handling: simply use no-arg constructor.
   // 使用默认的构造函数
   return instantiateBean(beanName, mbd);
}

第一行会再次调用resolveBeanClass尝试去获取bean里面的class对象，之后看看class的访问修饰符，检查是否有权通过反射创建private的Class，如果bean使用了java自带的函数式接口Supplier，即工厂方法，就会调用工厂方法里的get方法来创建bean实例

1
2
3
4
5
6
7
8
9
10
java复制代码@FunctionalInterface
public interface Supplier<T> {

    /**
     * Gets a result.
     *
     * @return a result
     */
    T get();
}

这里我们没有用到Supplier，就会看一下BeanDefinition里有没有定义Spring里的工厂方法，如果有则通过factory-method来返回实例。

如果不是上述两种方式，如果传入的args参数为空就会来到synchronized代码块，先判断一下先前解析配置成BeanDefinition实例的时候，有没有获取到已经解析的构造函数，如果有就会调用

1
java复制代码return autowireConstructor(beanName, mbd, null, null);

进行有参构造函数的解析。

之后会使用带参的构造函数进行装配或者无参的构造函数进行装配。

1
java复制代码return instantiateBean(beanName, mbd);

进入到调用无参构造函数的方法里：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码protected BeanWrapper instantiateBean(final String beanName, final RootBeanDefinition mbd) {
   try {
      Object beanInstance;
      final BeanFactory parent = this;
      if (System.getSecurityManager() != null) {
         beanInstance = AccessController.doPrivileged((PrivilegedAction<Object>) () ->
               getInstantiationStrategy().instantiate(mbd, beanName, parent),
               getAccessControlContext());
      }
      else {
         //使用指定的策路模式来初始化实例，默认用的是SimplelnstantiationStrategy的cglib方法
         beanInstance = getInstantiationStrategy().instantiate(mbd, beanName, parent);
      }
      BeanWrapper bw = new BeanWrapperImpl(beanInstance);
      initBeanWrapper(bw);
      return bw;
   }
   catch (Throwable ex) {
      throw new BeanCreationException(
            mbd.getResourceDescription(), beanName, "Instantiation of bean failed", ex);
   }
}

instantiate默认调用的是SimpleInstantiationStrategy类中的方法，在方法里会首先判断是否有look-up method等使用其他bean的替换方法的情况，如果有的话会使用cglib重写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
java复制代码@Override
public Object instantiate(RootBeanDefinition bd, @Nullable String beanName, BeanFactory owner) {
   // Don't override the class with CGLIB if no overrides.
   // 如果Bean定义里面的方法没有被覆盖，则不需要CGLUB来重写
   if (!bd.hasMethodOverrides()) {
      Constructor<?> constructorToUse;
      synchronized (bd.constructorArgumentLock) {
         // 获取对象的构造方法或工厂方法
         constructorToUse = (Constructor<?>) bd.resolvedConstructorOrFactoryMethod;
         if (constructorToUse == null) {
            //使 用反射机制获取Bean的类，看看是否是接口
            final Class<?> clazz = bd.getBeanClass();
            if (clazz.isInterface()) {
               throw new BeanInstantiationException(clazz, "Specified class is an interface");
            }
            try {
               if (System.getSecurityManager() != null) {
                  constructorToUse = AccessController.doPrivileged(
                        (PrivilegedExceptionAction<Constructor<?>>) clazz::getDeclaredConstructor);
               }
               else {
                  constructorToUse = clazz.getDeclaredConstructor();
               }
               bd.resolvedConstructorOrFactoryMethod = constructorToUse;
            }
            catch (Throwable ex) {
               throw new BeanInstantiationException(clazz, "No default constructor found", ex);
            }
         }
      }
      // 使用BeanUtils，最终调用newInstance方法通过反射来获取实例
      return BeanUtils.instantiateClass(constructorToUse);
   }
   else {
      // Must generate CGLIB subclass.
      return instantiateWithMethodInjection(bd, beanName, owner);
   }
}

再回到instantiateBean方法，获取到了创建好的bean实例之后，就会将其包装到BeanWrapper里，包装好了之后还回去初始化
请添加图片描述

1
2
3
4
java复制代码protected void initBeanWrapper(BeanWrapper bw) {
   bw.setConversionService(getConversionService());
   registerCustomEditors(bw);
}

initBeanWrapper主要是给wrapper设定上自定义类型转换工具

instantiateBean最终创建好的beanWrapper，此时就完成了createBeanInstance的调用。

回到doCreateBean，此时就会将创建好的instanceWrapper的bean实例类型传入到applyMergedBeanDefinitionPostProcessors(mbd, beanType, beanName);

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

文章简介

上一篇文章我们了解了进程和线程的发展历史、线程的生命周期、线程的优势和使用场景，这一篇，我们从Java层面更进一步了解线程的使用

内容导航

  1. 并发编程的挑战
  2. 线程在Java中的使用

并发编程的挑战

引入多线程的目的在第一篇提到过，就是为了充分利用CPU是的程序运行得更快，当然并不是说启动的线程越多越好。在实际使用多线程的时候，会面临非常多的挑战

线程安全问题

线程安全问题值的是当多个线程访问同一个对象时，如果不考虑这些运行时环境采用的调度方式或者这些线程将如何交替执行，并且在代码中不需要任何同步操作的情况下，这个类都能够表现出正确的行为，那么这个类就是线程安全的
比如下面的代码是一个单例模式，在代码的注释出，如果多个线程并发访问，则会出现多个实例。导致无法实现单例的效果

1
2
3
4
5
6
7
8
9
10
java复制代码public class SingletonDemo {
   private static SingletonDemo singletonDemo=null;
   private SingletonDemo(){}
    public static SingletonDemo getInstance(){
        if(singletonDemo==null){/***线程安全问题***/
           singletonDemo=new SingletonDemo();
        }
        return singletonDemo;
    }
}

通常来说，我们把多线程编程中的线程安全问题归类成如下三个，至于每一个问题的本质，在后续的文章中我们会单独讲解

  1. 原子性
  2. 可见性
  3. 有序性

上下文切换问题

在单核心CPU架构中，对于多线程的运行是基于CPU时间片切换来实现的伪并行。由于时间片非常短导致用户以为是多个线程并行执行。而一次上下文切换，实际就是当前线程执行一个时间片之后切换到另外一个线程，并且保存当前线程执行的状态这个过程。上下文切换会影响到线程的执行速度，对于系统来说意味着会消耗大量的CPU时间

减少上下文切换的方式

  1. 无锁并发编程，在多线程竞争锁时，会导致大量的上下文切换。避免使用锁去解决并发问题可以减少上下文切换
  2. CAS算法，CAS是一种乐观锁机制，不需要加锁
  3. 使用与硬件资源匹配合适的线程数

死锁

在解决线程安全问题的场景中，我们会比较多的考虑使用锁，因为它使用比较简单。但是锁的使用如果不恰当，则会引发死锁的可能性，一旦产生死锁，就会造成比较严重的问题：产生死锁的线程会一直占用锁资源，导致其他尝试获取锁的线程也发生死锁，造成系统崩溃

以下是死锁的简单案例

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
java复制代码public class DeadLockDemo {
    //定义锁对象
    private final Object lockA = new Object();
    private final Object lockB = new Object();
    private void deadLock(){
        new Thread(()->{
            synchronized (lockA){
                try {
                    Thread.sleep(4000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (lockB){
                    System.out.println("Lock B");
                }
            }
        }).start();
        new Thread(()->{
            synchronized (lockB){
                synchronized (lockA){
                    System.out.println("Lock A");
                }
            }
        }).start();
    }
    public static void main(String[] args) {
        new DeadLockDemo().deadLock();
    }
}

通过jstack分析死锁

1.首先通过jps获取当前运行的进程的pid

1
2
3
4
cmd复制代码6628 Jps
17588 RemoteMavenServer
19220 Launcher
19004 DeadLockDemo

2.jstack打印堆栈信息,输入 jstack19004, 会打印如下日志，可以很明显看到死锁的信息提示

1
2
3
4
5
6
7
8
cmd复制代码Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x000000001d461e68 (object 0x000000076b310df8, a java.lang.Object),
  which is held by "Thread-0"
"Thread-0":
  waiting to lock monitor 0x000000001d463258 (object 0x000000076b310e08, a java.lang.Object),
  which is held by "Thread-1"

解决死锁的手段
1.保证多个线程按照相同的顺序获取锁
2.设置获取锁的超时时间，超过设定时间以后自动释放
3.死锁检测

资源限制

资源限制主要指的是硬件资源和软件资源，在开发多线程应用时，程序的执行速度受限于这两个资源。硬件的资源限制无非就是磁盘、CPU、内存、网络；软件资源的限制有很多，比如数据库连接数、计算机能够支持的最大连接数等
资源限制导致的问题最直观的体现就是前面说的上下文切换，也就是CPU资源和线程资源的严重不均衡导致频繁上下文切换，反而会造成程序的运行速度下降

资源限制的主要解决方案，就是缺啥补啥。CPU不够用，可以增加CPU核心数；一台机器的资源有限，则增加多台机器来做集群。

线程在Java中的使用

在Java中实现多线程的方式比较简单，因为Java中提供了非常方便的API来实现多线程。
1.继承Thread类实现多线程
2.实现Runnable接口
3.实现Callable接口通过Future包装器来创建Thread线程，这种是带返回值的线程
4.使用线程池ExecutorService

继承Thread类

继承Thread类，然后重写run方法，在run方法中编写当前线程需要执行的逻辑。最后通过线程实例的start方法来启动一个线程

1
2
3
4
5
6
7
8
9
10
11
java复制代码public class ThreadDemo extends Thread{
    @Override
    public void run() {
        //重写run方法，提供当前线程执行的逻辑
        System.out.println("Hello world");
    }
    public static void main(String[] args) {
        ThreadDemo threadDemo=new ThreadDemo();
        threadDemo.start();
    }
}

Thread类其实是实现了Runnable接口，因此Thread自己也是一个线程实例，但是我们不能直接用 newThread().start()去启动一个线程，原因很简单，Thread类中的run方法是没有实际意义的，只是一个调用通过构造函数传递寄来的另一个Runnable实现类的run方法，这块的具体演示会在Runnable接口的代码中看到

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码public
class Thread implements Runnable {
    /* What will be run. */
    private Runnable target;
    ...
    @Override
    public void run() {
        if (target != null) {
            target.run();
        }
    }
    ...

实现Runnable接口

如果需要使用线程的类已经继承了其他的类，那么按照Java的单一继承原则，无法再继承Thread类来实现线程，所以可以通过实现Runnable接口来实现多线程

1
2
3
4
5
6
7
8
9
10
11
java复制代码public class RunnableDemo implements Runnable{
    @Override
    public void run() {
        //重写run方法，提供当前线程执行的逻辑
        System.out.println("Hello world");
    }
    public static void main(String[] args) {
        RunnableDemo runnableDemo=new RunnableDemo();
        new Thread(runnableDemo).start();
    }
}

上面的代码中，实现了Runnable接口，重写了run方法；接着为了能够启动RunnableDemo这个线程，必须要实例化一个Thread类，通过构造方法传递一个Runnable接口实现类去启动，Thread的run方法就会调用target.run来运行当前线程,代码在上面.

实现Callable接口

在有些多线程使用的场景中，我们有时候需要获取异步线程执行完毕以后的反馈结果，也许是主线程需要拿到子线程的执行结果来处理其他业务逻辑，也许是需要知道线程执行的状态。那么Callable接口可以很好的实现这个功能

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码public class CallableDemo implements Callable<String>{
    @Override
    public String call() throws Exception {
        return "hello world";
    }
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        Callable<String> callable=new CallableDemo();
        FutureTask<String> task=new FutureTask<>(callable);
        new Thread(task).start();
        System.out.println(task.get());//获取线程的返回值
    }
}

在上面代码案例中的最后一行 task.get()就是获取线程的返回值，这个过程是阻塞的，当子线程还没有执行完的时候，主线程会一直阻塞直到结果返回

使用线程池

为了减少频繁创建线程和销毁线程带来的性能开销，在实际使用的时候我们会采用线程池来创建线程，在这里我不打算展开多线程的好处和原理，我会在后续的文章中单独说明。

1
2
3
4
5
6
7
8
java复制代码public class ExecutorServiceDemo {
    public static void main(String[] args) throws ExecutionException, InterruptedException {
        //创建一个固定线程数的线程池
        ExecutorService pool = Executors.newFixedThreadPool(1);
        Future future=pool.submit(new CallableDemo()); 
        System.out.println(future.get());
    }
}

pool.submit有几个重载方法，可以传递带返回值的线程实例，也可以传递不带返回值的线程实例，源代码如下

1
2
3
java复制代码/*01*/Future<?> submit(Runnable task);
/*02*/<T> Future<T> submit(Runnable task, T result);
/*03*/<T> Future<T> submit(Callable<T> task);

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战

🤞 个人主页：@青Cheng序员石头

🤞 粉丝福利：加粉丝群 一对一问题解答，获取免费的丰富简历模板、提高学习资料等，做好新时代的卷卷王！

上一篇文章Hi，你想要的在线创建架构图都在这儿！（二），点击穿越过去。

八、Lucidchart

Lucidchart这款产品来自国外，它同样可以帮助用户绘制包括流程图、实体模型、UML、思维导图等多种图表的绘制工作,除此之外，上百种模板一定会加快的你的创作过程。并且Chrome浏览器插件市场提供了这个插件。

image.png

image.png
国内的Process On与它有很多相似的地方，互联网的世界谈不上谁抄袭谁，看看谁的创新以及细节做的好吧！另外Lucidchart与亿图图示经常有人也会去比较，其实功能大题一致，区分下来，亿图有社区的加成，Lucidchart有文件克隆等高级功能。

image.png

Lucidchart也是基础功能免费，如果要使用到一些高级功能，同样也是需要付费订阅的。价格对比Process On 和亿图图示，是要贵了一大截，个人去试试，再去决定用哪个吧！

九、Creately

使用Creately也能相当容易地创建基础结构图或流程图。它同样是一款优秀的绘制产品图形的在线工具，绘制的图形更为丰富，支持UML图、Mindmap图、SWOT图、产品原型图、流程图等等多种类型。

就我个人而言，我比较它的UI风格，看起来很清新，颜色搭配有视觉的舒适感。

image.png

其提供了1000个专业的模板，实现团队和客户无缝协作。无论你是工程师、产品、IT、设计师、教育、HR，你都能在这儿实现你的图表设计。

image.png

接下来的在线创建架构图的工具还会有：

  • Coggle
  • Mindmeister
  • yED

朋友，你用的是哪一种呢？评论留言你常用的工具，你认为最好的在线画图工具！

少年，没看够？点击石头的详情介绍，随便点点看看，说不定有惊喜呢？欢迎支持点赞/关注/评论，有你们的支持是我更文最大的动力，多谢啦！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

Redis 的事务就是将多个命令序列化，按顺序执行，并且它们在执行的过程中，不会被其他客户端发来的命令请求所打断。

一个事务从开始到执行会经历以下三个阶段：

  • 开始事务，使用 MULTI命令。
  • 命令入队，正常的操作命令。
  • 执行事务， EXEC命令。

也可以在 EXEC 之前用 DISCARD 放弃这个事务。

另外需要注意的是，

  1. 如果入队过程中命令报错了，执行时会直接报错，所有的命令都不会执行。
  2. 如果入队过程中没有命令报错，而在执行过程中，某个命令执行失败，则不影响其他命令的执行。

下面练习一下 redis 处理秒杀商品的案例。

秒杀商品

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
python复制代码def handle_buy_product(user):
    """
    抢购商品
    """
    product_number = redis_client.get(PRODUCT_NUMBER_KEY)
    # 未设置商品数目时，秒杀尚未开始
    if product_number is None:
        print("秒杀尚未开始")
        return False
    # 如果用户已经秒杀成功了
    if redis_client.sismember(SUCCESS_USER_KEY, user):
        print("你已秒杀成功，不能重复购买")
        return False
    # 如果库存不足，秒杀失败
    if int(product_number) <= 0:
        print("没有库存了")
        return False
    # 商品数量减1
    redis_client.decr(PRODUCT_NUMBER_KEY)
    # 记录秒杀成功的用户
    redis_client.sadd(SUCCESS_USER_KEY, user)
    return True

使用 locust 模拟高并发场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
python复制代码from locust import HttpUser, task


class BuyProductUser(HttpUser):
    @task()
    def buy(self):
        self.client.post("/buy")


if __name__ == "__main__":
    import os

    os.system("locust -f locust_test.py --host=http://localhost:8000")

可以发现会出现超卖的情况，也就是商品库存被扣到负数。

使用事务解决

我们可以使用 pipeline，watch， multi， 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
python复制代码def handle_buy_product(user):
    """
    抢购商品
    """
    pipe = redis_client.pipeline()
    try:
        # 增加监视
        pipe.watch(PRODUCT_NUMBER_KEY)
        # 获取库存
        product_number = pipe.get(PRODUCT_NUMBER_KEY)
        # 未设置商品数目时，秒杀尚未开始
        if product_number is None:
            print("秒杀尚未开始")
            return False
        # 如果用户已经秒杀成功了
        if redis_client.sismember(SUCCESS_USER_KEY, user):
            print("你已秒杀成功，不能重复购买")
            return False
        # 如果库存不足，秒杀失败
        if int(product_number) <= 0:
            print("没有库存了")
            return False
        # 事务
        pipe.multi()
        # 商品数量减1
        pipe.decr(PRODUCT_NUMBER_KEY)
        # 记录秒杀成功的用户
        pipe.sadd(SUCCESS_USER_KEY, user)
        # 执行
        pipe.execute()
    except WatchError:
        print("秒杀失败")
        return False
    finally:
        pipe.reset()
    return True

实验结果可以发现，不会出现超卖问题了，但是，可以观察到，会出现很多次的秒杀失败，商品数量下降的也比较慢。

使用 lua 锁

我们可以使用 lua 锁（悲观锁）来解决上面的问题。

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
python复制代码def handle_buy_product(user):
    """
    抢购商品
    """
    try:
        with redis_client.lock("my-lock-key", blocking_timeout=5) as lock:
            # 获取库存
            product_number = redis_client.get(PRODUCT_NUMBER_KEY)
            # 未设置商品数目时，秒杀尚未开始
            if product_number is None:
                print("秒杀尚未开始")
                return False
            # 如果用户已经秒杀成功了
            if redis_client.sismember(SUCCESS_USER_KEY, user):
                print("你已秒杀成功，不能重复购买")
                return False
            # 如果库存不足，秒杀失败
            if int(product_number) <= 0:
                print("没有库存了")
                return False
            # 商品数量减1
            redis_client.decr(PRODUCT_NUMBER_KEY)
            # 记录秒杀成功的用户
            redis_client.sadd(SUCCESS_USER_KEY, user)
            return True
    except LockError:
        print("秒杀失败")
        return False

代码可见：github.com/luxu1220/re…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战」

最近，想复习一下C语言，所以笔者将会在掘金每天更新一篇关于C语言的文章！ 各位初学C语言的大一新生，以及想要复习C语言/C++知识的不要错过哦！ 夯实基础，慢下来就是快！

5.地址，数组与指针的概念

问：地址可以比较大小吗？
1
2
3
c复制代码地址可以比较大小，地址本质是个16进制的数值
   
指针中存储的是地址，地址可以看成一个数据，因此是可以比较大小的
指针和数组的关系？

指针和数组毫无关系

数组：

1
2
3
c复制代码数组：是一块连续的空间，放的是相同类型的元素
    
数组和数组大小，元素类型，元素个数有关系
1
2
3
4
5
6
7
8
c复制代码如： 1.int arr[10]; 
数组arr的类型为： int[10]   去掉数组名就是数组的类型
      2.int arr2[5]
 数组arr2的类型为：int[5] 
    arr和arr2是不同的数组
    
   int(*pa)[10] = &arr;  //pa是数组指针
   int(*pa2)[5] = &arr2;

去掉数组名->数组的类型

去掉数组名和元素个数->数组存放的元素类型

关于数组名的理解

数组名是首元素地址

但是有两个例外：

1.sizeof(数组名)-这里的数组名代表的是整个数组，计算的是整个数组的大小，单位是字节

2.&数组名-取出的是整个数组的地址

&数组名+1：跳过整个数组

指针：

指针：是一个变量，存放地址

指针是变量，是变量就有地址。所以指针变量也有自己的地址

指针变量的大小：4byte（32位平台） 8byte（64byte平台）

1
2
3
4
c复制代码int a = 10;
int* p =&a;
// * 说明p是指针，int：说明p指向的类型为int类型
int** pp = &p;	//pp就是二级指针

image.png

image.png

6.指针数组

指针数组是数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
c复制代码int main()
{
    int a = 10;
    int b = 20;
    int c = 30;
    int* arr[3] = {&a,&b,&c};
    int i = 0;
    for(i = 0;i < 3;i++)
    {
        printf("%d\n",*(arr[i]));
        //也可以不加括号，因为[]的优先级比*高
        printf("%d\n",*arr[i]);
    }
    return 0;
}

7.指针与结构体

关于结构体

结构体可以在main函数内部定义，但不建议

结构体类型定义并不占用空间 实际定义结构体变量才占用空间****

全局的结构体，未初始化，编译器会给它的变量默认初始化为0

**静态区的变量不初始化默认为0 **

静态区：static，全局变量

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
c复制代码typedef struct Book
{
	char name[20];
	float price;
	char author[20];
}Stu; b1, b2;			//b1,b2是全局变量，存放在静态区
//typedef重命名类型名字  Stu ==struct Book 类型名   

//传值
void Print(Stu b1)
{
	printf("%f %s %s\n", b1.price, b1.author, b1.name);
}
//传址-结构体指针接收
void Print2(Stu* b1)
{
	printf("%f %s %s\n", b1->price, b1->author, b1->name);
}
int main()
{
	struct Book b3 = { "Mango",19.0,"Lemon" };	//b3是局部变量，存放在栈区

	Print(b3);//传值
	Print2(&b3);	//传址
	return 0;
}

对于上面两种传结构体的方式：传值，传址

传地址：只传过去4个字节，浪费的空间小

传值：直接开辟一个和原结构体相同大小的空间，浪费空间，会导致压栈问题

所以我们更倾向于传址方式

今天就先到这吧~感谢你能看到这里！希望对你有所帮助！欢迎老铁们点个关注订阅这个专题！ 同时欢迎大佬们批评指正！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

IO、零拷贝、ByteBuffer、DirectByteBuffer、MappedByteBuffer

前言

在Java中经常会提到零拷贝，这个词在不同的层面有不同的含义：

  1. Java 堆内和堆外之间的零拷贝
  2. 数据在用户空间和内核空间的零拷贝
  3. 处理分段的数据，拼接、切片时的零拷贝

JVM堆内外之间的数据零拷贝

内存布局基础

JVM虚拟机是由C++语言编写的，对操作系统来说只是一个普通的C++程序，所以除了Java的内存模型外，JVM整体使用的内存也符合C语言的堆栈区分配。看下面这张经典的C语言内存布局图：

不要把JVM的堆栈和C语言的堆栈弄混了，因为JVM属于C++程序，而我们所谓的Java堆实际上是一个C++对象，所以属于C语言的堆之内。至于Java线程的栈分配在C语言的堆还是栈上就看具体的虚拟机实现了，这个其实区别不大。

对于JVM的堆我们暂且叫做：Java Heap，之外的堆叫做C Heap。

对应的，ByteBuffer有allocate方法用来申请堆内和堆外缓冲区。

Java Heap和C Heap哪个效率更高？

其实差别不大，两个都是由malloc申请来的内存，可以理解为Java Heap属于C Heap的一部分，所以两者的读写效率肯定没什么差别。

但Java Heap有一个很重要的特性就是GC，在堆内GC的时候可能会移动其中的对象。 这点很关键，因为这意味着我们的Java对象的内存地址并不是固定的。

这也解释了一个常见的疑问：‘Java的hashcode是否是内存地址？’，答案是否定的，Java的HashCode其实不是内存地址。因为Java规范要求应用运行其间hashcode值不能变，但Java对象的内存地址是会变化的。

为什么会在堆内外之间发生数据拷贝

由于JVM只是一个普通的用户程序，所以涉及到系统功能时JVM必须把功能委托给操作系统提供的系统调用执行，这里我们研究一下IO操作中的write和read函数。

结论

由于下面会涉及到源码分析，不感兴趣的可以跳过，这里先说下结论：

由于JVM GC其间会移动对象的地址，包括byte[]，而内核无法感知到内存的移动，很可能会导致数据错误。所以我们在以byte[]的形式写入数据时必须先把数据拷贝到不受JVM堆控制的堆外内存中，这部分就是我们说的C heap，而DirectByteBuffer正处于这片区域。

同样的，read的时候，我们也要保证在系统往缓冲区写入的时候我们不能gc移动内存，否则数据不知道写到了哪里，所以也会导致拷贝发生。

源码分析

Java版本：openjdk-17

我们分析两块代码：

FileOutputStream/FileInputStream的读写以及SocketChannel和FileChannel的读写。

首先是FileOutputStream：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
java复制代码 /**

 * Writes a sub array as a sequence of bytes.

 * @param b the data to be written

 * @param off the start offset in the data

 * @param len the number of bytes that are written

 * @param append {@code true} to first advance the position to the

 *     end of file

 * @throws    IOException If an I/O error has occurred.

 */

private native void writeBytes(byte b[], int off, int len, boolean append)

    throws IOException;

我们可以看到，writeBytes调用的是native方法，FileInputStream的readBytes也是一样的。

我们找到对应的C源码文件，src\java.base\share\native\libjava\FileOutputStream.c

1
2
3
4
5
6
7
8
9
10
11
12
13
arduino复制代码#include "io_util.h"



JNIEXPORT void JNICALL

Java_java_io_FileOutputStream_writeBytes(JNIEnv *env,

    jobject this, jbyteArray bytes, jint off, jint len, jboolean append) {

    writeBytes(env, this, bytes, off, len, append, fos_fd);

}

对应的在io_util.c中，其中包含了读写IO的方法，其中读和写的逻辑差不多，都是先开辟缓冲区，然后复制，调用系统调用。

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
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
ini复制代码

/* The maximum size of a stack-allocated buffer.

 */

#define BUF_SIZE 8192



//读函数

jint

readBytes(JNIEnv *env, jobject this, jbyteArray bytes,

          jint off, jint len, jfieldID fid)

{

    jint nread;

    char stackBuf[BUF_SIZE];

    char *buf = NULL;

    FD fd;

    //省略一些越界检查

    //开辟堆外缓冲区，如果小于BUF_SIZE，直接在栈上，否则用malloc在堆上开辟

    if (len == 0) {

        return 0;

    } else if (len > BUF_SIZE) {

        buf = malloc(len);

        if (buf == NULL) {

            JNU_ThrowOutOfMemoryError(env, NULL);

            return 0;

        }

    } else {

        buf = stackBuf;

    }



    fd = getFD(env, this, fid);

    if (fd == -1) {

        JNU_ThrowIOException(env, "Stream Closed");

        nread = -1;

    } else {

        //执行系统调用,对应handleRead，看下面

        nread = IO_Read(fd, buf, len);

        if (nread > 0) {

            //从堆外(C HEAP)拷贝数据到JVM堆内

            (*env)->SetByteArrayRegion(env, bytes, off, nread, (jbyte *)buf);

        } else if (nread == -1) {

            JNU_ThrowIOExceptionWithLastError(env, "Read error");

        } else { /* EOF */

            nread = -1;

        }

    }



    if (buf != stackBuf) {

        free(buf);

    }

    return nread;

}



//写函数

void

writeBytes(JNIEnv *env, jobject this, jbyteArray bytes,

           jint off, jint len, jboolean append, jfieldID fid)

{

    jint n;

    char stackBuf[BUF_SIZE];

    char *buf = NULL;

    FD fd;

    //。。。省略一些检查

    //开辟缓冲区，小数组直接在栈上，大数组用malloc申请堆内存

    if (len == 0) {

        return;

    } else if (len > BUF_SIZE) {

        buf = malloc(len);

        if (buf == NULL) {

            JNU_ThrowOutOfMemoryError(env, NULL);

            return;

        }

    } else {

        buf = stackBuf;

    }

    //关键在此，会把我们传入的数组(Java Heap)拷贝到刚刚申请的堆外内存(C Heap)里

    (*env)->GetByteArrayRegion(env, bytes, off, len, (jbyte *)buf);



    if (!(*env)->ExceptionOccurred(env)) {

        off = 0;

        while (len > 0) {

            fd = getFD(env, this, fid);

            if (fd == -1) {

                JNU_ThrowIOException(env, "Stream Closed");

                break;

            }

            //系统调用

            if (append == JNI_TRUE) {

                n = IO_Append(fd, buf+off, len);

            } else {

                n = IO_Write(fd, buf+off, len);

            }

            if (n == -1) {

                JNU_ThrowIOExceptionWithLastError(env, "Write error");

                break;

            }

            off += n;

            len -= n;

        }

    }

    //清理缓冲区

    if (buf != stackBuf) {

        free(buf);

    }

}



//其中IO_WRITE和IO_APPEND都对应io_util_md.c下的handleWrite方法

ssize_t

handleWrite(FD fd, const void *buf, jint len)

{

    ssize_t result;

    //终于看到了熟悉的write，这里就是系统调用了

    RESTARTABLE(write(fd, buf, len), result);

    return result;

}

//对应IO_READ

ssize_t

handleRead(FD fd, void *buf, jint len)

{

    ssize_t result;

    RESTARTABLE(read(fd, buf, len), result);

    return result;

}

其它IO类：

FileChannelImpl、SocketChannelImpl读写都使用的是IOUtil类，进去看一下：

里面会判断是否为DirectByteBuffer，如果不是就申请一个，当然，这里系统会维持一个DirectByteBuffer的缓存，如果小数据量会直接分配，没必要每次都malloc，大数据量则重新申请一块堆外内存。

然后调用NativeDispatcher的write方法，代码实现在FileDispatcherImpl.c里，也很难简单就不去说了。

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
scss复制代码static int write(FileDescriptor fd, ByteBuffer src, long position,

                 boolean directIO, boolean async, int alignment,

                 NativeDispatcher nd)

    throws IOException

{

    //关键！！！，这里会判断使用的是否是DirectByteBuffer，如果是调用另一个方法

    if (src instanceof DirectBuffer) {

        return writeFromNativeBuffer(fd, src, position, directIO, async, alignment, nd);

    }



    //否则使用navtiveBuffer拷贝需要写入的数据

    // Substitute a native buffer

 int pos = src.position();

    int lim = src.limit();

    assert (pos <= lim);

    int rem = (pos <= lim ? lim - pos : 0);

    ByteBuffer bb;

    //申请directBuffer

    if (directIO) {

        Util.checkRemainingBufferSizeAligned(rem, alignment);

        bb = Util.getTemporaryAlignedDirectBuffer(rem, alignment);

    } else {

        bb = Util.getTemporaryDirectBuffer(rem);

    }

    try {

        //拷贝

        bb.put(src);

        bb.flip();

        // Do not update src until we see how many bytes were written

 src.position(pos);



        int n = writeFromNativeBuffer(fd, bb, position, directIO, async, alignment, nd);

        if (n > 0) {

            // now update src

 src.position(pos + n);

        }

        return n;

    } finally {

        Util.offerFirstTemporaryDirectBuffer(bb);

    }

}

怎么避免堆内外拷贝

由上面的代码也能分析出来，只要你在支持缓冲区操作的地方使用DirectByteBuffer就可以了，而对于面向流的byte[]数组参数的方法，拷贝是没法避免的。

另外，DirectByteBuffer有一定的缓存，所以小数据的读写不会调用malloc，复制速度也会比较快。

用户空间和内核空间的零拷贝

我们同样先来梳理一下为什么IO时会有拷贝发生，以最典型的文件读写读写为例，当我们读取文件、处理数据、再写回文件的操作流程如下：

  1. 用户态调用系统调用-read
  2. 内核给DMA控制器发送读命令
  3. DMA负责控制硬盘，读取数据到内核缓冲区，完成后通知CPU
  4. CPU将数据搬运到用户态缓冲区
  5. 用户处理数据
  6. 调用write系统调用
  7. 内核复制用户数据到内核缓冲区
  8. 使用DMA将数据写入到硬盘
  9. 返回给用户

网络IO也是一样的，只不过硬盘变成了网卡而已。

具体逻辑如下图：

可以看到，当我们完成一次读，修改，写的流程时，来回内核缓冲区拷贝了两次，如果再加上堆内外的拷贝，又要再加两次，这性能损失是很恐怖的。

为什么要发生拷贝？

这个问题其实很复杂，可以再写一个文章了，简单来说：

用户空间是绝对无法直接访问内核空间的，但是内核空间可以直接访问用户空间或者说任意一块物理内存。

系统调用会涉及到特权等级的切换（由用户态到内核态），内核需要为其开辟新的堆栈空间，然后将参数复制到内核堆栈，交给内核处理。参数的复制很简单也很好理解，因为两者不能共享栈，复制速度也都很快，但为什么要参数中指针指向的缓冲区数据也要复制呢？

这块儿其实很复杂，和安全性有关，但主要的原因应该是：

用户空间的内存可能并不指向物理内存，直接访问时可能产生缺页异常。但是Linux内核禁止在中断时产生缺页异常，否则会产生打印oops错误。这就要求我们用户的缓冲区数据必须要存在内存中，而这个实际上很难控制，所以就会直接把数据复制到内核缓冲区中。

这块儿细说真的可以再开一个坑了，，简单的贴一下linux内核源码，有空再写一篇。

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
arduino复制代码//缺页异常处理函数

asmlinkage void

do_page_fault(unsigned long address, unsigned long mmcsr,

          long cause, struct pt_regs *regs)

{

    //省略一堆。。

    //这里注释已经说的很清楚了，不允许在内核中执行缺页中断

    /* If we're in an interrupt context, or have no user context,

       we must not take the fault.  */

    if (!mm || faulthandler_disabled())

        goto no_context;

}

//打印oops

 no_context:

    /* Oops. The kernel tried to access some bad page. We'll have to

       terminate things with extreme prejudice.  */

    printk(KERN_ALERT "Unable to handle kernel paging request at "

           "virtual address %016lx\n", address);

    die_if_kernel("Oops", regs, cause, (unsigned long*)regs - 16);

    do_exit(SIGKILL);

内存映射：MappedByteBuffer

MappedByteBuffer是DirectByteBuffer的子类，所以MappedByteBuffer也属于堆外内存。

MappedByteBuffer的原理是mmap()，即内存映射。为了避免拷贝数据，我们可以让内核和用户空间共享同一块缓冲区，即：在内核种开辟一个缓冲区，然后将这同一块物理内存同时映射到内核空间和用户空间，这样用户的数据修改对内核是立即可见的，就节省了拷贝，而且可以避免系统调用，相当于共享内存了。

由于我们把文件的内容直接映射到了内存中，修改起来也会非常的快。

sendfile

Java中对应的是FileChannel.transfer();

这个主要用于不要处理数据，单纯读写的情景，如：文件的拷贝

试想一下，如果我们只是单纯的下载文件，从网卡读取数据然后再写入到硬盘中，中间不需要修改数据，所以没有必要让数据在内核和用户空间来回复制，直接让内核帮我们把网卡数据写入到硬盘即可，中间没必要用户态干预，节省了拷贝和系统调用次数。

所以FileChannel.transfer的速度是很快的。

代码测试：

测试环境：windows11，java17

用不同的方式拷贝一个700M的文件，结果

stream用时：1658ms

byteBuffer拷贝用时：1665ms

directByteBuffer拷贝用时：1565ms

channel拷贝用时：910ms

100M文件，结果：

stream用时：422ms

byteBuffer拷贝用时：419ms

directByteBuffer拷贝用时：384ms

transfer拷贝用时：129ms

注意，transfer默认一次最大传输2GB。另外不同的拷贝方式主要区别在于数据在内存中拷贝的次数和系统调用的次数不同，如果磁盘的速度占主要部分，时间差距就没有那么明显了，因为内存中的数据拷贝要比硬盘快上几个量级。

代码如下：

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
ini复制代码

public static void copyByStream(File source, File dest) throws IOException {

    if (!dest.exists()) {

        dest.createNewFile();

    }

    try (var input = new BufferedInputStream(new FileInputStream(source));

         var output = new BufferedOutputStream(new FileOutputStream(dest));) {

        byte[] buf = new byte[1024 * 8];

        int len = 0;

        while ((len = input.read(buf)) != -1) {

            output.write(buf, 0, len);

        }

        output.flush();

    }

}



public static void copyByByteBuffer(File source, File dest) throws IOException {

    if (!dest.exists()) {

        dest.createNewFile();

    }

    try (var in = new FileInputStream(source);

         var out = new FileOutputStream(dest);

         var sourceChannel = in.getChannel();

         var destChannel = out.getChannel();) {

        ByteBuffer buffer = ByteBuffer.allocate(1024 * 8);

        while (sourceChannel.read(buffer) != -1) {

            buffer.flip();

            destChannel.write(buffer);

            buffer.flip();

        }

    }

}



public static void copyByDirectByteBuffer(File source, File dest) throws IOException {

    if (!dest.exists()) {

        dest.createNewFile();

    }

    try (var in = new FileInputStream(source);

         var out = new FileOutputStream(dest);

         var sourceChannel = in.getChannel();

         var destChannel = out.getChannel();) {

        ByteBuffer buffer = ByteBuffer.allocateDirect(1024 * 8);

        while (sourceChannel.read(buffer) != -1) {

            buffer.flip();

            destChannel.write(buffer);

            buffer.flip();

        }

    }

}



public static void copyByTransfer(File source, File dest) throws IOException {

    if (!dest.exists()) {

        dest.createNewFile();

    }

    try (var in = new FileInputStream(source);

         var out = new FileOutputStream(dest);

         var sourceChannel = in.getChannel();

         var destChannel = out.getChannel();) {

        long count = 0;

        while (count < source.length()) {

            count += destChannel.transferFrom(sourceChannel,count,source.length());

        }

    }

}

用户空间内的零拷贝

这个主要是指netty的零拷贝，因为网络数据或者说大部分IO数据都是一段一段的，分散成多个ByteBuffer，而我们做数据转换时可能需要获取全部数据才能处理，这中间就会涉及到很多次的拷贝：先把每个ByteBuffer储存起来，然后再统一拷贝到大的ByteBuffer中一块处理。

Netty在这方面做的比较好，自己设计了一个ByteBuf和CompositeByteBuf。

原理也很简单，CompositeByteBuf内部维护了多个ByteBuf，操作时维护一个统一的读写指针，就像操作一个ByteBuf一样，可以快速的进行合并、切片。

1
2
3
4
5
6
7
8
9
10
11
ini复制代码ByteBuf header = Unpooled.buffer(1024);

ByteBuf body = Unpooled.buffer(1024);

//合并，并不会复制

CompositeByteBuf buf = Unpooled.compositeBuffer();

buf.addComponent(header);

buf.addComponent(body);

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

❓ 实现以下接口 ❔

1
2
3
4
5
6
7
8
9
10
c复制代码// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

❗ 实现代码 ❕

  ❤ BinaryTreeSize ❤

    🔑 核心思想1 ：使用前序 || 中序 || 后序遍历，全局变量记录

    ❌ 但是以下代码有 Bug ：如果采用前序重复遍历 2 次

    ✔ 经查，问题出在全局变量上，这里只需要在第 2 次遍历时置 0 即可

    ⚠ 在以后的知识面更大后，其实你会发现这种操作还有线程安全的问题

    🔑 核心思想 2：函数使用带返回值的方式，其内部的递归本质上是一个后序遍厉

  ❤ BinaryTreeLeafSize ❤

    🔑 核心思想 ：以 left 和 right 为标志，如果都为 NULL，则累加

  ❤ BinaryTreeLevelKSize ❤

    🔑 核心思想 ：求当前树的第 k 层 = 左子树的第 k - 1 层 +　右子树的第 k - 1 层 (当 k = 1 时，说明此层就是目标层)

  ❤ BinaryTreeDepth ❤

    🔑 核心思想 ：当前树的深度 = max (左子树的深度，右子树的深度) + 1

  ❤ BinaryTreeFind ❤

    🔑 核心思想 ：

      1、先判断是不是当前节点，是就返回；

      2、先去左树找，找到就返回

      3、左树没找到，再找右树

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
c复制代码#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
// 二叉树节点个数
	//1、前序递归遍历
int sz1 = 0;
void BinaryTreeSize1(BTNode* root)
{
	if (root == NULL)
		return;
	else
		sz1++;
	BinaryTreeSize1(root->left);
	BinaryTreeSize1(root->right);
}
//2、中序递归遍历
int sz2 = 0;
void BinaryTreeSize2(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeSize2(root->left);
	if (root != NULL)
		sz2++;
	BinaryTreeSize2(root->right);
}
//3、后序递归遍历
int sz3 = 0;
void BinaryTreeSize3(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeSize3(root->left);
	BinaryTreeSize3(root->right);
	if (root != NULL)
		sz3++;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子节点个数
int BinaryTreeLeaSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLeaSize(root->left) + BinaryTreeLeaSize(root->right);
	}
}
//二叉树第k层节点个数
int BinaryTreeLeveLKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLeveLKSize(root->left, k - 1) + BinaryTreeLeveLKSize(root->right, k - 1);
}
//二叉树的深度/高度 
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* retleft = BinaryTreeFind(root->left, x);
	if (retleft)
	{
		return retleft;
	}
	BTNode* retright = BinaryTreeFind(root->right, x);
	if (retright)
	{
		return retright;
	}
	return NULL;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;

	return node1;
}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
int main()
{
	BTNode* root = CreatBinaryTree();
	//遍厉前中后序输出二叉树节点的个数
	BinaryTreeSize1(root);
	BinaryTreeSize2(root);
	BinaryTreeSize3(root);
	printf("BinaryTreeSize:%d\n", sz1);
	printf("BinaryTreeSize:%d\n", sz2);
	printf("BinaryTreeSize:%d\n", sz3);
	printf("-----------------cur-----------------\n");
	//优化二叉树节点的个数
	printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
	printf("-----------------cur-----------------\n");
	//二叉树叶子节点个数
	printf("BinaryTreeLeaSize:%d\n", BinaryTreeLeaSize(root));
	printf("-----------------cur-----------------\n");
	//二叉树第k层节点个数
	printf("BinaryTreeLeveLKSize:%d\n", BinaryTreeLeveLKSize(root, 3));
	printf("-----------------cur-----------------\n");
	//二叉树的深度/高度 
	printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
	printf("-----------------cur-----------------\n");
	// 二叉树查找值为x的节点
	BTNode* ret = BinaryTreeFind(root, 'D');
	if(ret)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}

	PreOrder(root);
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」。

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。本文详细介绍了队列的特性，并且使用Java语言分别实现了基于顺序结构和链式结构的队列。

1 队列的概述

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车，而后来的人将会排在你朋友后面。队列的工作原理与此相同。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,……,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。

在这里插入图片描述

因为队列属于线性表，因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现，比如JUC中的各种阻塞、非阻塞队列。在生产环境中，各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。

关于Java 栈的数据结构，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

2 队列的顺序存储结构实现

2.1 队列的顺序存储结构概述

和栈不同的是，队列的入队和出队操作在不同端。采用数组来实现时，如果和实现栈的思想一样，如果队头在数组元素最大索引处，那么入队列就是将元素添加到最大索引后的索引处，不需要移动元素，此时时间复杂度为Ｏ(1)；但是出队列就要在数组头部了，此时将会移动全部元素，时间复杂度为O(n)。如果队头在数组元素的起始索引处，那么出队列到时变快了，但是入队列的时间复杂度却又变成O(n)了。

因此，这里要灵活处理对头或者队尾，不再是固定在数组起始索引或者最大索引处，应该是可变的，此时需要添加外部指针用来保存“队头”和“队尾”。操作数据的时候只需要操作队头和队尾就行了，这样入队和出队的时间复杂度都是O(1)。

按照上面的做法，队头和队尾是不用固定了，入队和出队操作确实很方便。但是可能造成索引溢出以及内存浪费，如下图：

在这里插入图片描述

可能会出现图上的情况，队头被移动到数组的中间，而队尾由于添加元素，移动到数组尾部，此时如果再次入队，由于数组索引溢出将会抛出ArrayIndexOutOfBoundsException，但是数组的前半部分空间却还没有使用，此时又造成了空间浪费。

上面这种溢出，称为“假溢出”。假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列解决了假溢出的问题，同时入队和出队时间都是O(1)。此时需要考虑的就只是数组的容量有限的问题了。

2.2 数组循环队列的简单实现

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
java复制代码/**
 * 数组实现的循环队列,为了方便,这里底层数组设计为不可扩展
 */
public class MyArrayLoopQueue<E> {

    /**
     * 采用数组实现链式存储
     */
    private final Object[] elements;

    /**
     * 容量
     */
    private final int capacity;

    /**
     * 队头元素索引
     */
    private int first;

    /**
     * 队尾元素索引
     */
    private int end;

    /**
     * 元素个数
     */
    private int size;

    /**
     * 构造器初始化数组
     *
     * @param capacity 容量
     */
    public MyArrayLoopQueue(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }


    /**
     * 入队,元素添加在队尾
     *
     * @param element 添加的元素
     * @return 添加成功返回true，添加失败返回false
     */
    public boolean add(E element) {
        //如果队列容量已满.添加失败返回false
        if (size == capacity) {
            return false;
        }
        if (size == 0) {
            /*如果是第一次放元素,则队头和队尾都指向索引0处的元素*/
            elements[end] = element;
        } else if (end + 1 == capacity) {
            /*如果end + 1等于capacity说明队尾空间满了，转向队头,队尾队尾索引置0，循环*/
            end = 0;
            elements[end] = element;
        } else {
            /*否则,队尾索引正常自增*/
            elements[++end] = element;
        }
        //size自增1
        size++;
        return true;
    }

    /**
     * 出队,删除队头元素
     *
     * @return 被移除的元素, 或者null
     */
    public E remove() {
        //队列是否已空
        if (size == 0) {
            // 返回null
            return null;
        }
        Object o = elements[first];
        //移除队头元素
        elements[first] = null;
        //如果队头索引+1之后等于capacity，重置队头索引，循环
        if (++first == capacity) {
            first = 0;
        }
        //如果出队列后队列为空,那么重置队头和队尾索引
        if (--size == 0) {
            first = 0;
            end = 0;
        }
        return (E) o;
    }

    /**
     * 返回队列元素数量
     *
     * @return
     */
    public int size() {
        return size;
    }


    /**
     * 清空队列
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
        first = 0;
        end = 0;
    }


    /**
     * 重写了toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size == 0) {
            stringBuilder.append("[ ]");
            return stringBuilder.toString();
        }
        stringBuilder.append("[ ");
        if (first < end) {
            for (int i = first; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        } else if (size == 1) {
            stringBuilder.append(elements[first]);
        } else {
            for (int i = first; i < capacity; i++) {
                stringBuilder.append(elements[i]);
                stringBuilder.append(", ");
            }
            for (int i = 0; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        }
        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }


    /**
     * 增强toString方法,用于测试
     *
     * @return
     */
    public String toStringPlus() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size == 0) {
            stringBuilder.append("[ ]");
            stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);
            return stringBuilder.toString();
        }
        stringBuilder.append("[ ");
        if (first < end) {
            for (int i = first; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        } else if (size == 1) {
            stringBuilder.append(elements[first]);
        } else {
            for (int i = first; i < capacity; i++) {
                stringBuilder.append(elements[i]);
                stringBuilder.append(", ");
            }
            for (int i = 0; i <= end; i++) {
                stringBuilder.append(elements[i]);
                if (i != end) {
                    stringBuilder.append(", ");
                }
            }
        }
        stringBuilder.append(" ]");
        stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);
        return stringBuilder.toString();
    }
}

2.2.1 测试

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
java复制代码MyArrayLoopQueue<Object> objectMyArrayLoopQueue = new 
MyArrayLoopQueue<>(4);
System.out.println("入队========>");
objectMyArrayLoopQueue.add(11);
objectMyArrayLoopQueue.add(22);
objectMyArrayLoopQueue.add(33);
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("出队========>");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("出队========>");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("入队========>");
objectMyArrayLoopQueue.add(44);
objectMyArrayLoopQueue.add(55);
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("入队========>");
objectMyArrayLoopQueue.add(null);
System.out.println(objectMyArrayLoopQueue.toStringPlus());

System.out.println("入队失败========>");
boolean add = objectMyArrayLoopQueue.add(77);
System.out.println(add);
System.out.println(objectMyArrayLoopQueue.toStringPlus());


System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());

3 队列的链式存储结构及实现

3.1 队列的链式存储结构概述

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

可以看出来，使用链式结构实现队列相比顺序结构的实现更加简单。

3.2 队列的链式存储结构简单实现

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
java复制代码/**
 * 队列的链式储存结构的简单单链表实现
 */
public class MySingleLinkedQueue<E> {

    /**
     * 空构造器,内部的节点均没有初始化,在第一次添加时才会初始化。
     */
    public MySingleLinkedQueue() {
    }

    /**
     * 元素个数
     */
    private int size;

    /**
     * 指向队头结点的引用
     */
    private Node<E> first;


    /**
     * 指向队尾结点的引用
     */
    private Node<E> end;

    /**
     * 单链表内部的节点
     */
    private static class Node<E> {
        //下一个结点的引用
        Node<E> next;
        //结点数据
        E data;

        //节点构造器
        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    /**
     * 入队，添加元素到单链表尾部
     *
     * @param e 要添加的元素
     */
    public void add(E e) {
        //创建新节点
        Node<E> newNode = new Node<>(e, null);
        if (end != null) {
            /*如果尾结点不为空*/
            end.next = newNode;
            //改变队尾节点引用
            end = newNode;
        } else {
            end = newNode;
            first = newNode;
        }
        ++size;
    }

    /**
     * 出队，删除单链表头部元素
     *
     * @return 被删除的元素
     */
    public E remove() {
        //如果头结点为空,抛出异常
        if (first == null) {
            throw new NoSuchElementException("队列已经为空");
        }
        E e = first.data;
        //改变队头节点引用
        first = first.next;
        //如果元素为0,则将队尾节点引用置空
        if (--size == 0) {
            end = null;
        }
        return e;
    }

    /**
     * 获取元素数量
     */
    public int size() {
        return size;
    }


    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size > 0) {
            Node<E> f = first;
            stringBuilder.append("[ ");
            for (int i = 0; i < size; i++) {
                stringBuilder.append(f.data);
                if (i != size - 1) {
                    stringBuilder.append(" , ");
                }
                f = f.next;
            }
            stringBuilder.append(" ]");
            return stringBuilder.toString();
        }
        return "[]";
    }
}

3.2.1 测试

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
java复制代码MySingleLinkedQueue<Object> objectMySingleLinkedQueue = new 
MySingleLinkedQueue<>();
System.out.println("入队========>");
objectMySingleLinkedQueue.add(11);
objectMySingleLinkedQueue.add(22);
objectMySingleLinkedQueue.add(33);
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("出队========>");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("出队========>");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("入队========>");
objectMySingleLinkedQueue.add(44);
objectMySingleLinkedQueue.add(55);
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("入队========>");
objectMySingleLinkedQueue.add(null);
System.out.println(objectMySingleLinkedQueue.toString());


System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());

System.out.println("出队异常========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());

4 总结

本文介绍了队列的基本概念，并且提供了简单的实现，队列属于一种特殊的线性表。“先来的数据先处理”是一种很常见的思路，所以队列的应用范围非常广泛，实际上我们能够直接接触到的队列的应用是要高于栈的应用的，比如各种并发队列，消息队列。另外在广度优先搜索算法中，通常就会从搜索候补中选择最早的数据作为下一个顶点。此时，在候补顶点的管理上就可以使用队列。

另外，关于Java 栈的数据结构，可以看这篇文章：数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。

相关文章：

  1. 《大话数据结构》
  2. 《算法图解》
  3. 《我的第一本算法书》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第21天，活动详情查看：2021最后一次更文挑战

注：本部分主要介绍SSIS项目升级(升级至SSIS2012)。因此不重点详细操作每一步（个人演示从一开始就是使用的 SSIS 2012）。但是关于项目部署模型的转换，可以详细了解下。

在本文中，将使用 SQL Server Data Tools —— 商业智能（SSDT-BI）或 Visual Studio 2012 将第一个 SSIS 项目转换为 SSIS2012。可以在此处查看 SSIS 2012中的新特性。如果想使用新的 SSIS 2012 目录(Catalog)，则项目必须遵循“项目部署模型”（将在本文中进行演示）。

使用 SSDT-BI 转换到 SSIS 2012

在本系列的第十三篇，SSIS变量概述中，我们从头创建了一个SSIS项目（My_Second_SSIS_Project）。首先，我们使用 SQL Server Data Tools–商业智能（SSDT-BI）将之前的名为My_First_SSIS_Project的SSIS项目转换为SSIS 2012。

至少有两种方法来进行SSIS项目转换：您可以从Windows资源管理器中通过 “打开方式”(Open With) 菜单打开解决方案文件（*.sln），也可以启动 SQL Server Data Tools– BI，然后从起始页上的 “打开项目” 链接中打开SSIS解决方案。在 SSIS变量概述 中，演示了如何从起始页创建新的SSIS项目，该过程与使用 “打开项目” 链接转换SSIS解决方案非常相似。此处使用 Windows资源管理器 进行演示。

下图显示了这种方法 —— 使用 Windows资源管理器 的 “打开方式” 菜单打开 Visual Studio解决方案文件 —— My_First_SSIS_Project.sln：

Figure 1

我更喜欢启动 SSDT-BI，然后打开要转换的SSIS项目（或解决方案）文件。在 Windows 8/2012 中，打开 Visual Studio 2012 的 SQL Server Data Tools，如图所示：

Figure 2

“开始页面” 有很多帮助信息，可以通过单击 “视图” 下拉菜单上的 “开始页面” 来查看 “开始页面”，如图所示：

Figure 3

起始页面包括一个打开现有项目的链接（“Open Project…”），如图所示：

Figure 4

SSDT-BI 将转换一个早期版本创建的 SSIS 项目。单击 Open Project 链接，然后浏览到 My_First_SSIS_Project SSIS 项目文件（或解决方案文件），如图所示：

Figure 5

SSDT-BI 警告，这是单向升级。一旦名为 My_First_SSIS_Project 的SSIS项目升级到 SSDT-BI 2012 格式后，将无法从 Business Intelligence Development Studio（BIDS）对其进行访问。

打开先前版本中构建的SSIS项目时，将显示下main所示的对话框：

Figure 6

回到过去（2008年），有可能将 SSIS项目 从 SSIS 2005 意外地更新到 SSIS 2008。这对某些开发人员来说很烦人，因为实际情况，几乎没有或根本没有警告说升级即将进行。开发人员抱怨（理所当然的是，这是一个悲剧性的疏忽），Microsoft对此进行了回应，添加了该警告信息的屏幕，以确保开发人员知道此升级是不可逆的。

SSIS项目升级后，您将无法再在以前的开发环境中打开SSIS项目。如果要维护SSIS项目的早期版本，则需要在进行升级之前制作项目的副本。更好的方法，可以考虑使用源代码控制。

每次从 SSDT-BI 中的非本地磁盘源打开SSIS项目时，下图所示的“安全警告”都会显示：

Figure 7

确认安全警告后，将在默认的Web浏览器中显示“迁移报告”，如图所示：

Figure 8

SSIS软件包升级向导（如图9所示）在显示迁移报告的同时启动：

Figure 9

单击下一步按钮继续。下一个屏幕包含要升级的 SSIS 软件包的列表，如图所示。默认情况下，应检查所有软件包，并且应该接受默认设置：

Figure 10

选择要升级的软件包后，单击“下一步”按钮继续。然后会显示用于管理升级的选项，保持默认选项即可：

Figure 11

我很少在 “选择包管理选项”(Select Package Management Options) 界面上更改默认选择。进行更改时，通常会添加 “验证升级的包”、“创建新包ID”(“Validate upgraded packages”, “Create new package ID”) 其中的一个或两个。除非同时升级与SSIS包连接的所有服务器，否则不需要更新连接字符串中的提供器(provider)名称（尽管多年来，我一直没有遇到升级提供者名称的问题，因为它们是向后兼容的）。验证升级的包是“双重检查”。会在操作结束时知道升级是否成功。我可能会选择创建一个新的包ID，以使我的SSIS包ID值在企业中保持唯一。

在执行时 —— 从文件系统、msdb数据库或SSIS包存储中执行时 —— 可以设置一个选项来验证包ID。如果在执行此验证的情况下执行SSIS包，则可能要保留原始包ID。通常，我会选中 “软件包失败时继续升级过程” 复选框。如果已开始此过程，则希望它升级尽可能多的包。如果要升级一个或多个SSIS包文件失败，可以手动升级或直接重建。总是将 “忽略配置” 复选框保持选中状态，在包升级完成后手动将SSIS包配置转换为包（或项目）参数。注意：仍然可以在 SSIS 2012 中配置和使用包配置。

单击“下一步”按钮继续。该向导将执行几秒钟（或几分钟），具体取决于要升级的SSIS软件包的数量及其复杂性。完成后，将显示“升级状态”界面，如图所示：

Figure 12

部署模型(Deployment Models)

打开 “My_First_SSIS_Project” —— 刚刚转换的SSIS项目，如图所示：

Figure 13

在解决方案资源管理器中，注意项目名称右边的文字“（package deployment model）”，如图所示：

Figure 14

Microsoft SSIS 团队在支持 SSIS 2012 中的向后兼容性方面做得非常出色。部署模型是这种向后兼容性的很大一部分。当从 SSIS 2008 导入 SSIS 包时，由于”包部署模型”，其行为将与2008年完全一样。

包部署模型(Package Deployment Model) 是 Microsoft 在 2005 至 2008 R2 的 SSIS 版本中用于SSIS包部署、执行和管理的名称。 SSIS 2012 支持包部署模型，即，可以在 SSIS 2012 中运行 SSIS 2008 包。有一些警告（不一定总是有警告），但是它们众所周知并且相对容易解决。例如，在包部署模型(Package Deployment Model)中执行的SSIS包不能利用 SSIS 2012 目录(SSIS 2012 Catalog)，不能使用项目级连接管理器(Project-level Connection Managers)，也不能使用项目或包参数(Project or Package Parameters)。

SSIS 2012 的默认部署模型是 项目部署模型(Project Deployment Model)。 Microsoft提供了在模型之间进行转换的向导。要将 My_First_SSIS_Project 转换为 Project Deployment Model，请在解决方案资源管理器中右键单击项目名称，然后单击 “转换为项目部署模型”(Convert to Project Deployment Model)，如图所示：

Figure 15

右键，将项目部署模型转换为包部署模型

启动 Project Conversion Wizard，如图所示：

Figure 16

项目转换向导的第一步是选择包：

Figure 17

下一步，是指定项目属性 —— 项目“保护级别”和“描述”属性(the project Protection Level and Description properties)：

Figure 18

如果SSIS项目包含”执行包任务”，则在下一步中它们将升级：

Figure 19

新的项目部署模型是需要更新”执行包任务”的主要原因。 SSIS 2012”执行包任务”包含一个新属性：引用类型(Reference Type)。

与以前的SSIS版本一样，子包可以从 文件系统或msdb数据库(file system or msdb database) 执行。“引用类型” 属性必须设置为 “外部引用”(External Reference)，才能执行存储在这些位置的子包。要引用与父包包含在相同的项目中的子包，需将“引用类型”设置为“项目引用”(Project Reference)。

通过 “项目转换向导” 中的此步骤，你可以将”包部署模型”的”外部引用”分配给”项目部署模型”的”项目引用”。

向导的接下来的两个步骤使我们能够将 Package Configuration 值转换为 参数(Parameters)，从下图开始：

Figure 20

上图所示的 Configurations 界面和下图所示的 Parameters 界面不适用于My_First_SSIS_Project，因为我们没有配置 Package Configurations。

Figure 21

由于在上一步中未创建任何参数，因此在下面所示的步骤中没有要配置的参数：

Figure 22

现在我们准备执行转换，如图所示：

Figure 23

转换完成后，将显示一个报告界面，显示转换结果。

同时，还将显示一个对话框，通知用户在 保存项目之前不会保存这些更改。保存项目的最好方法是保存所有内容（单击”文件”->”全部保存”）。

Figure 24

转换完SSIS项目后，将会出现在 “解决方案资源管理器” 中，项目名称右边的括号中没有文本，如图所示：

Figure 25

在解决方案资源管理器中还要注意几个新的虚拟对象：Project.params 和 “连接管理器”(Connection Managers)。

总结

在本文中，我们使用 SQL Server 2012 Data Tools–BI 将第一个 SSIS 项目 —— My_First_SSIS_Project —— 转换为SSIS 2012；然后将导入的SSIS项目从“包部署模型”转换为“项目部署模型”。

翻译参考

本文主要参考翻译自 The Stairway to Integration Services 系列文章的原文 An Overview of Project Conversion - Level 14 of the Stairway to Integration Services，目的在于对 SSIS 有一个全面清晰的认识，所有内容在原文的基础上进行实操，由于版本差异、个人疑问等多种原因，未采用完全翻译的原则，同时也会对文中内容进行适当修改，希望最终可以更有利于学习和了解 SSIS，

感谢支持！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%