精华内容
下载资源
问答
  • Lua源码分析

    2018-01-12 23:08:57
    Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析Lua源码分析
  • lvs源码分析 ipvs源码分析

    热门讨论 2012-07-28 22:45:00
    lvs源码分析,介绍的很详细。均衡调度算法,IPVS 的连接管理,IPVS 的协议管理,IPVS 的数据包发送,IPVS 的应用管理
  • 当tomcat启动的时候会创建servlet,调用其init方法,我们知道DispatchServlet就是一个...1.创建容器源码分析源码分析 url类图 源码分析 找到了init方法: public final void init() throws ServletException

    上一篇:01-SpringMVC初识https://blog.csdn.net/fsjwin/article/details/109559961

    当tomcat启动的时候会创建servlet,调用其init方法,我们知道DispatchServlet就是一个Servlet,所以我们猜测一下应该会在init方法中创建容器。

    1.创建容器源码分析源码分析

    1. url类图
      在这里插入图片描述
    2. 源码分析

    在这里插入图片描述
    找到了init方法:

        public final void init() throws ServletException {
            PropertyValues pvs = new HttpServletBean.ServletConfigPropertyValues(this.getServletConfig(), this.requiredProperties);
            if (!pvs.isEmpty()) {
                try {
                    BeanWrapper bw = PropertyAccessorFactory.forBeanPropertyAccess(this);
                    ResourceLoader resourceLoader = new ServletContextResourceLoader(this.getServletContext());
                    bw.registerCustomEditor(Resource.class, new ResourceEditor(resourceLoader, this.getEnvironment()));
                    this.initBeanWrapper(bw);
                    bw.setPropertyValues(pvs, true);
                } catch (BeansException var4) {
                    if (this.logger.isErrorEnabled()) {
                        this.logger.error("Failed to set bean properties on servlet '" + this.getServletName() + "'", var4);
                    }
    
                    throw var4;
                }
            }
    
            this.initServletBean();
        }
    

    在这里插入图片描述
    调用:initServletBean()方法

    protected final void initServletBean() throws ServletException {
            this.getServletContext().log("Initializing Spring " + this.getClass().getSimpleName() + " '" + this.getServletName() + "'");
            if (this.logger.isInfoEnabled()) {
                this.logger.info("Initializing Servlet '" + this.getServletName() + "'");
            }
    
            long startTime = System.currentTimeMillis();
    
            try {
                this.webApplicationContext = this.initWebApplicationContext();
                this.initFrameworkServlet();
            } catch (RuntimeException | ServletException var4) {
                this.logger.error("Context initialization failed", var4);
                throw var4;
            }
    
            if (this.logger.isDebugEnabled()) {
                String value = this.enableLoggingRequestDetails ? "shown which may lead to unsafe logging of potentially sensitive data" : "masked to prevent unsafe logging of potentially sensitive data";
                this.logger.debug("enableLoggingRequestDetails='" + this.enableLoggingRequestDetails + "': request parameters and headers will be " + value);
            }
    
            if (this.logger.isInfoEnabled()) {
                this.logger.info("Completed initialization in " + (System.currentTimeMillis() - startTime) + " ms");
            }
    
        }
    

    在这里插入图片描述
    初始化容器。

    protected WebApplicationContext initWebApplicationContext() {
            WebApplicationContext rootContext = WebApplicationContextUtils.getWebApplicationContext(this.getServletContext());
            WebApplicationContext wac = null;
            if (this.webApplicationContext != null) {
                wac = this.webApplicationContext;
                if (wac instanceof ConfigurableWebApplicationContext) {
                    ConfigurableWebApplicationContext cwac = (ConfigurableWebApplicationContext)wac;
                    if (!cwac.isActive()) {
                        if (cwac.getParent() == null) {
                            cwac.setParent(rootContext);
                        }
    
                        this.configureAndRefreshWebApplicationContext(cwac);
                    }
                }
            }
    
            if (wac == null) {
                wac = this.findWebApplicationContext();
            }
    
            if (wac == null) {
                wac = this.createWebApplicationContext(rootContext);
            }
    
            if (!this.refreshEventReceived) {
                synchronized(this.onRefreshMonitor) {
                    this.onRefresh(wac);
                }
            }
    
            if (this.publishContext) {
                String attrName = this.getServletContextAttributeName();
                this.getServletContext().setAttribute(attrName, wac);
            }
    
            return wac;
        }
    

    在这里插入图片描述
    有了servletContext我们就可以为所欲为了。哈哈。不懂的回去补servlet。

    当然在创建容器的过程中会扫描注解,放入我们的容器中。

    2.调用过程源码分析

    1. 页面发起请求有service方法处理HttpServlet.service(ServletRequest req, ServletResponse res)
     @Override
        public void service(ServletRequest req, ServletResponse res)
            throws ServletException, IOException
        {
            HttpServletRequest  request;
            HttpServletResponse response;
            
            if (!(req instanceof HttpServletRequest &&
                    res instanceof HttpServletResponse)) {
                throw new ServletException("non-HTTP request or response");
            }
    
            request = (HttpServletRequest) req;
            response = (HttpServletResponse) res;
    
            service(request, response);
        }
    
    1. 调用FrameworkServlet.service(HttpServletRequest request, HttpServletResponse response)
        protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
            HttpMethod httpMethod = HttpMethod.resolve(request.getMethod());
            if (httpMethod != HttpMethod.PATCH && httpMethod != null) {
                super.service(request, response);
            } else {
                this.processRequest(request, response);
            }
    
        }
    
    1. 调用this.doService()方法
     protected final void processRequest(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
            long startTime = System.currentTimeMillis();
            Throwable failureCause = null;
            LocaleContext previousLocaleContext = LocaleContextHolder.getLocaleContext();
            LocaleContext localeContext = this.buildLocaleContext(request);
            RequestAttributes previousAttributes = RequestContextHolder.getRequestAttributes();
            ServletRequestAttributes requestAttributes = this.buildRequestAttributes(request, response, previousAttributes);
            WebAsyncManager asyncManager = WebAsyncUtils.getAsyncManager(request);
            asyncManager.registerCallableInterceptor(FrameworkServlet.class.getName(), new FrameworkServlet.RequestBindingInterceptor());
            this.initContextHolders(request, localeContext, requestAttributes);
    
            try {
                this.doService(request, response);
            } catch (IOException | ServletException var16) {
                failureCause = var16;
                throw var16;
            }
    
    1. 调用DispatcherServlet.doService(HttpServletRequest request, HttpServletResponse response)方法
     protected void doService(HttpServletRequest request, HttpServletResponse response) throws Exception {
            this.logRequest(request);
            Map<String, Object> attributesSnapshot = null;
            if (WebUtils.isIncludeRequest(request)) {
                attributesSnapshot = new HashMap();
                Enumeration attrNames = request.getAttributeNames();
    
                label95:
                while(true) {
                    String attrName;
                    do {
                        if (!attrNames.hasMoreElements()) {
                            break label95;
                        }
    
                        attrName = (String)attrNames.nextElement();
                    } while(!this.cleanupAfterInclude && !attrName.startsWith("org.springframework.web.servlet"));
    
                    attributesSnapshot.put(attrName, request.getAttribute(attrName));
                }
            }
    
            request.setAttribute(WEB_APPLICATION_CONTEXT_ATTRIBUTE, this.getWebApplicationContext());
            request.setAttribute(LOCALE_RESOLVER_ATTRIBUTE, this.localeResolver);
            request.setAttribute(THEME_RESOLVER_ATTRIBUTE, this.themeResolver);
            request.setAttribute(THEME_SOURCE_ATTRIBUTE, this.getThemeSource());
            if (this.flashMapManager != null) {
                FlashMap inputFlashMap = this.flashMapManager.retrieveAndUpdate(request, response);
                if (inputFlashMap != null) {
                    request.setAttribute(INPUT_FLASH_MAP_ATTRIBUTE, Collections.unmodifiableMap(inputFlashMap));
                }
    
                request.setAttribute(OUTPUT_FLASH_MAP_ATTRIBUTE, new FlashMap());
                request.setAttribute(FLASH_MAP_MANAGER_ATTRIBUTE, this.flashMapManager);
            }
    
            try {
                this.doDispatch(request, response);
            } finally {
                if (!WebAsyncUtils.getAsyncManager(request).isConcurrentHandlingStarted() && attributesSnapshot != null) {
                    this.restoreAttributesAfterInclude(request, attributesSnapshot);
                }
    
            }
    
        }
    
    1. this. doDispatch(HttpServletRequest request, HttpServletResponse response) 在这方法中会调用我的controller中的对应方法,生成ModleAndView对象,请求转发过去。
     protected void doDispatch(HttpServletRequest request, HttpServletResponse response) throws Exception {
            HttpServletRequest processedRequest = request;
            HandlerExecutionChain mappedHandler = null;
            boolean multipartRequestParsed = false;
            WebAsyncManager asyncManager = WebAsyncUtils.getAsyncManager(request);
    
            try {
                try {
                    ModelAndView mv = null;
                    Object dispatchException = null;
    
                    try {
                        processedRequest = this.checkMultipart(request);
                        multipartRequestParsed = processedRequest != request;
                        mappedHandler = this.getHandler(processedRequest);
                        if (mappedHandler == null) {
                            this.noHandlerFound(processedRequest, response);
                            return;
                        }
    
                        HandlerAdapter ha = this.getHandlerAdapter(mappedHandler.getHandler());
                        String method = request.getMethod();
                        boolean isGet = "GET".equals(method);
                        if (isGet || "HEAD".equals(method)) {
                            long lastModified = ha.getLastModified(request, mappedHandler.getHandler());
                            if ((new ServletWebRequest(request, response)).checkNotModified(lastModified) && isGet) {
                                return;
                            }
                        }
    
                        if (!mappedHandler.applyPreHandle(processedRequest, response)) {
                            return;
                        }
    
                        mv = ha.handle(processedRequest, response, mappedHandler.getHandler());
                        if (asyncManager.isConcurrentHandlingStarted()) {
                            return;
                        }
    
                        this.applyDefaultViewName(processedRequest, mv);
                        mappedHandler.applyPostHandle(processedRequest, response, mv);
                    } catch (Exception var20) {
                        dispatchException = var20;
                    } catch (Throwable var21) {
                        dispatchException = new NestedServletException("Handler dispatch failed", var21);
                    }
    
                    this.processDispatchResult(processedRequest, response, mappedHandler, mv, (Exception)dispatchException);
                } catch (Exception var22) {
                    this.triggerAfterCompletion(processedRequest, response, mappedHandler, var22);
                } catch (Throwable var23) {
                    this.triggerAfterCompletion(processedRequest, response, mappedHandler, new NestedServletException("Handler processing failed", var23));
                }
    
            } finally {
                if (asyncManager.isConcurrentHandlingStarted()) {
                    if (mappedHandler != null) {
                        mappedHandler.applyAfterConcurrentHandlingStarted(processedRequest, response);
                    }
                } else if (multipartRequestParsed) {
                    this.cleanupMultipart(processedRequest);
                }
    
            }
        }
    

    3. 总结

    1. 创建过程-利于理解和记忆
      在这里插入图片描述

    2. 请求工程-利于理解和记忆
      在这里插入图片描述
      下一篇: 03-SpringMVC视图解析器的使用https://blog.csdn.net/fsjwin/article/details/109562410

    展开全文
  • Carson带你学Java:手把手带你源码分析 HashMap 1.7

    万次阅读 多人点赞 2018-02-26 08:31:23
    今天,我将带来HashMap 的全部源码分析,希望你们会喜欢。 本文基于版本 JDK 1.7,即 Java 7 关于版本 JDK 1.8,即 Java 8,具体请看文章Java源码分析:关于 HashMap 1.8 的重大更新 目录 ...

    前言

    • HashMapJavaAndroid 开发中非常常见
    • 今天,我将带来HashMap 的全部源码分析,希望你们会喜欢。
    1. 本文基于版本 JDK 1.7,即 Java 7
    2. 关于版本 JDK 1.8,即 Java 8,具体请看文章Java源码分析:关于 HashMap 1.8 的重大更新

    目录

    示意图


    1. 简介

    • 类定义
    public class HashMap<K,V>
             extends AbstractMap<K,V> 
             implements Map<K,V>, Cloneable, Serializable
    
    • 主要介绍

    示意图

    • HashMap 的实现在 JDK 1.7JDK 1.8 差别较大
    • 今天,我将主要讲解 JDK 1.7HashMap 的源码解析

    关于 JDK 1.8HashMap 的源码解析请看文章:Java源码分析:关于 HashMap 1.8 的重大更新


    2. 数据结构

    2.1 具体描述

    HashMap 采用的数据结构 = 数组(主) + 单链表(副),具体描述如下

    该数据结构方式也称:拉链法

    示意图

    2.2 示意图

    示意图

    2.3 存储流程

    注:为了让大家有个感性的认识,只是简单的画出存储流程,更加详细 & 具体的存储流程会在下面源码分析中给出

    示意图

    2.4 数组元素 & 链表节点的 实现类

    • HashMap中的数组元素 & 链表节点 采用 Entry类 实现,如下图所示

    示意图

    1. HashMap的本质 = 1个存储Entry类对象的数组 + 多个单链表
    2. Entry对象本质 = 1个映射(键 - 值对),属性包括:键(key)、值(value) & 下1节点( next) = 单链表的指针 = 也是一个Entry对象,用于解决hash冲突
    • 该类的源码分析如下

    具体分析请看注释

    /** 
     * Entry类实现了Map.Entry接口
     * 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
    **/  
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;  // 键
        V value;  // 值
        Entry<K,V> next; // 指向下一个节点 ,也是一个Entry对象,从而形成解决hash冲突的单链表
        int hash;  // hash值
      
        /** 
         * 构造方法,创建一个Entry 
         * 参数:哈希值h,键值k,值v、下一个节点n 
         */  
        Entry(int h, K k, V v, Entry<K,V> n) {  
            value = v;  
            next = n;  
            key = k;  
            hash = h;  
        }  
      
        // 返回 与 此项 对应的键
        public final K getKey() {  
            return key;  
        }  
    
        // 返回 与 此项 对应的值
        public final V getValue() {  
            return value;  
        }  
      
        public final V setValue(V newValue) {  
            V oldValue = value;  
            value = newValue;  
            return oldValue;  
        }  
        
       /** 
         * equals()
         * 作用:判断2个Entry是否相等,必须key和value都相等,才返回true  
         */ 
          public final boolean equals(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry e = (Map.Entry)o;  
            Object k1 = getKey();  
            Object k2 = e.getKey();  
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
                Object v1 = getValue();  
                Object v2 = e.getValue();  
                if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                    return true;  
            }  
            return false;  
        }  
        
        /** 
         * hashCode() 
         */ 
        public final int hashCode() { 
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
        }  
      
        public final String toString() {  
            return getKey() + "=" + getValue();  
        }  
      
        /** 
         * 当向HashMap中添加元素时,即调用put(k,v)时, 
         * 对已经在HashMap中k位置进行v的覆盖时,会调用此方法 
         * 此处没做任何处理 
         */  
        void recordAccess(HashMap<K,V> m) {  
        }  
      
        /** 
         * 当从HashMap中删除了一个Entry时,会调用该函数 
         * 此处没做任何处理 
         */  
        void recordRemoval(HashMap<K,V> m) {  
        } 
    
    }
    

    3. 具体使用

    3.1 主要使用API(方法、函数)

    V get(Object key); // 获得指定键的值
    V put(K key, V value);  // 添加键值对
    void putAll(Map<? extends K, ? extends V> m);  // 将指定Map中的键值对 复制到 此Map中
    V remove(Object key);  // 删除该键值对
    
    boolean containsKey(Object key); // 判断是否存在该键的键值对;是 则返回true
    boolean containsValue(Object value);  // 判断是否存在该值的键值对;是 则返回true
     
    Set<K> keySet();  // 单独抽取key序列,将所有key生成一个Set
    Collection<V> values();  // 单独value序列,将所有value生成一个Collection
    
    void clear(); // 清除哈希表中的所有键值对
    int size();  // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
    boolean isEmpty(); // 判断HashMap是否为空;size == 0时 表示为 空 
    
    

    3.2 使用流程

    • 在具体使用时,主要流程是:
    1. 声明1个 HashMap的对象
    2. HashMap 添加数据(成对 放入 键 - 值对)
    3. 获取 HashMap 的某个数据
    4. 获取 HashMap 的全部数据:遍历HashMap
    • 示例代码
    import java.util.Collection;
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    import java.util.Set;
    
    public class HashMapTest {
    
        public static void main(String[] args) {
          /**
            * 1. 声明1个 HashMap的对象
            */
            Map<String, Integer> map = new HashMap<String, Integer>();
    
          /**
            * 2. 向HashMap添加数据(成对 放入 键 - 值对)
            */
            map.put("Android", 1);
            map.put("Java", 2);
            map.put("iOS", 3);
            map.put("数据挖掘", 4);
            map.put("产品经理", 5);
    
           /**
            * 3. 获取 HashMap 的某个数据
            */
            System.out.println("key = 产品经理时的值为:" + map.get("产品经理"));
    
          /**
            * 4. 获取 HashMap 的全部数据:遍历HashMap
            * 核心思想:
            * 步骤1:获得key-value对(Entry) 或 key 或 value的Set集合
            * 步骤2:遍历上述Set集合(使用for循环 、 迭代器(Iterator)均可)
            * 方法共有3种:分别针对 key-value对(Entry) 或 key 或 value
            */
    
            // 方法1:获得key-value的Set集合 再遍历
            System.out.println("方法1");
            // 1. 获得key-value对(Entry)的Set集合
            Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
    
            // 2. 遍历Set集合,从而获取key-value
            // 2.1 通过for循环
            for(Map.Entry<String, Integer> entry : entrySet){
                System.out.print(entry.getKey());
                System.out.println(entry.getValue());
            }
            System.out.println("----------");
            // 2.2 通过迭代器:先获得key-value对(Entry)的Iterator,再循环遍历
            Iterator iter1 = entrySet.iterator();
            while (iter1.hasNext()) {
                // 遍历时,需先获取entry,再分别获取key、value
                Map.Entry entry = (Map.Entry) iter1.next();
                System.out.print((String) entry.getKey());
                System.out.println((Integer) entry.getValue());
            }
    
    
            // 方法2:获得key的Set集合 再遍历
            System.out.println("方法2");
    
            // 1. 获得key的Set集合
            Set<String> keySet = map.keySet();
    
            // 2. 遍历Set集合,从而获取key,再获取value
            // 2.1 通过for循环
            for(String key : keySet){
                System.out.print(key);
                System.out.println(map.get(key));
            }
    
            System.out.println("----------");
    
            // 2.2 通过迭代器:先获得key的Iterator,再循环遍历
            Iterator iter2 = keySet.iterator();
            String key = null;
            while (iter2.hasNext()) {
                key = (String)iter2.next();
                System.out.print(key);
                System.out.println(map.get(key));
            }
    
    
            // 方法3:获得value的Set集合 再遍历
            System.out.println("方法3");
    
            // 1. 获得value的Set集合
            Collection valueSet = map.values();
    
            // 2. 遍历Set集合,从而获取value
            // 2.1 获得values 的Iterator
            Iterator iter3 = valueSet.iterator();
            // 2.2 通过遍历,直接获取value
            while (iter3.hasNext()) {
                System.out.println(iter3.next());
            }
    
        }
    
    
    }
    
    // 注:对于遍历方式,推荐使用针对 key-value对(Entry)的方式:效率高
    // 原因:
       // 1. 对于 遍历keySet 、valueSet,实质上 = 遍历了2次:1 = 转为 iterator 迭代器遍历、2 = 从 HashMap 中取出 key 的 value 操作(通过 key 值 hashCode 和 equals 索引)
       // 2. 对于 遍历 entrySet ,实质 = 遍历了1次 = 获取存储实体Entry(存储了key 和 value )
    
    • 运行结果
    方法1
    Java2
    iOS3
    数据挖掘4
    Android1
    产品经理5
    ----------
    Java2
    iOS3
    数据挖掘4
    Android1
    产品经理5
    方法2
    Java2
    iOS3
    数据挖掘4
    Android1
    产品经理5
    ----------
    Java2
    iOS3
    数据挖掘4
    Android1
    产品经理5
    方法3
    2
    3
    4
    1
    5
    

    下面,我们按照上述的使用过程,对一个个步骤进行源码解析


    4. 基础知识:HashMap中的重要参数(变量)

    • 在进行真正的源码分析前,先讲解HashMap中的重要参数(变量)
    • HashMap中的主要参数 = 容量、加载因子、扩容阈值
    • 具体介绍如下
    // 1. 容量(capacity): HashMap中数组的长度
    // a. 容量范围:必须是2的幂 & <最大容量(2的30次方)
    // b. 初始容量 = 哈希表创建时的容量
      // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
      static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
      // 最大容量 =  2的30次方(若传入的容量过大,将被最大值替换)
      static final int MAXIMUM_CAPACITY = 1 << 30;
    
    // 2. 加载因子(Load factor):HashMap在其容量自动增加前可达到多满的一种尺度
    // a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低(因为链表变长了)
    // b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高(链表不长)
      // 实际加载因子
      final float loadFactor;
      // 默认加载因子 = 0.75
      static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 3. 扩容阈值(threshold):当哈希表的大小 ≥ 扩容阈值时,就会扩容哈希表(即扩充HashMap的容量) 
    // a. 扩容 = 对哈希表进行resize操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数
    // b. 扩容阈值 = 容量 x 加载因子
      int threshold;
    
    // 4. 其他
     // 存储数据的Entry类型 数组,长度 = 2的幂
     // HashMap的实现方式 = 拉链法,Entry数组上的每个元素本质上是一个单向链表
      transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  
     // HashMap的大小,即 HashMap中存储的键值对的数量
      transient int size;
     
    
    
    • 参数示意图

    示意图

    • 此处 详细说明 加载因子

    示意图


    5. 源码分析

    • 本次的源码分析主要是根据 使用步骤 进行相关函数的详细分析
    • 主要分析内容如下:

    示意图

    • 下面,我将对每个步骤内容的主要方法进行详细分析

    步骤1:声明1个 HashMap的对象

    /**
      * 函数使用原型
      */
      Map<String,Integer> map = new HashMap<String,Integer>();
    
     /**
       * 源码分析:主要是HashMap的构造函数 = 4个
       * 仅贴出关于HashMap构造函数的源码
       */
      public class HashMap<K,V>
          extends AbstractMap<K,V>
          implements Map<K,V>, Cloneable, Serializable{
    
        // 省略上节阐述的参数
        
      /**
         * 构造函数1:默认构造函数(无参)
         * 加载因子 & 容量 = 默认 = 0.75、16
         */
        public HashMap() {
            // 实际上是调用构造函数3:指定“容量大小”和“加载因子”的构造函数
            // 传入的指定容量 & 加载因子 = 默认
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 
        }
    
        /**
         * 构造函数2:指定“容量大小”的构造函数
         * 加载因子 = 默认 = 0.75 、容量 = 指定大小
         */
        public HashMap(int initialCapacity) {
            // 实际上是调用指定“容量大小”和“加载因子”的构造函数
            // 只是在传入的加载因子参数 = 默认加载因子
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
            
        }
    
        /**
         * 构造函数3:指定“容量大小”和“加载因子”的构造函数
         * 加载因子 & 容量 = 自己指定
         */
        public HashMap(int initialCapacity, float loadFactor) {
    
            // HashMap的最大容量只能是MAXIMUM_CAPACITY,哪怕传入的 > 最大容量
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
    
            // 设置 加载因子
            this.loadFactor = loadFactor;
            // 设置 扩容阈值 = 初始容量
            // 注:此处不是真正的阈值,是为了扩展table,该阈值后面会重新计算,下面会详细讲解  
            threshold = initialCapacity;   
    
            init(); // 一个空方法用于未来的子对象扩展
        }
    
        /**
         * 构造函数4:包含“子Map”的构造函数
         * 即 构造出来的HashMap包含传入Map的映射关系
         * 加载因子 & 容量 = 默认
         */
    
        public HashMap(Map<? extends K, ? extends V> m) {
    
            // 设置容量大小 & 加载因子 = 默认
            this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                    DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    
            // 该方法用于初始化 数组 & 阈值,下面会详细说明
            inflateTable(threshold);
    
            // 将传入的子Map中的全部元素逐个添加到HashMap中
            putAllForCreate(m);
        }
    }
    
    • 注:
      1. 此处仅用于接收初始容量大小(capacity)、加载因子(Load factor),但仍无真正初始化哈希表,即初始化存储数组table
      2. 此处先给出结论:真正初始化哈希表(初始化存储数组table)是在第1次添加键值对时,即第1次调用put()时。下面会详细说明

    至此,关于HashMap的构造函数讲解完毕。


    步骤2:向HashMap添加数据(成对 放入 键 - 值对)

    • 添加数据的流程如下

    注:为了让大家有个感性的认识,只是简单的画出存储流程,更加详细 & 具体的存储流程会在下面源码分析中给出

    示意图

    • 源码分析
     /**
       * 函数使用原型
       */
       map.put("Android", 1);
            map.put("Java", 2);
            map.put("iOS", 3);
            map.put("数据挖掘", 4);
            map.put("产品经理", 5);
    
       /**
         * 源码分析:主要分析: HashMap的put函数
         */
        public V put(K key, V value)
    (分析1)// 1. 若 哈希表未初始化(即 table为空) 
            // 则使用 构造函数时设置的阈值(即初始容量) 初始化 数组table  
            if (table == EMPTY_TABLE) { 
            inflateTable(threshold); 
        }  
            // 2. 判断key是否为空值null
    (分析2)// 2.1 若key == null,则将该键-值 存放到数组table 中的第1个位置,即table [0]
            // (本质:key = Null时,hash值 = 0,故存放到table[0]中)
            // 该位置永远只有1个value,新传进来的value会覆盖旧的value
            if (key == null)
                return putForNullKey(value);
    
    (分析3) // 2.2 若 key ≠ null,则计算存放数组 table 中的位置(下标、索引)
            // a. 根据键值key计算hash值
            int hash = hash(key);
            // b. 根据hash值 最终获得 key对应存放的数组Table中位置
            int i = indexFor(hash, table.length);
    
            // 3. 判断该key对应的值是否已存在(通过遍历 以该数组元素为头结点的链表 逐个判断)
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
    (分析4)// 3.1 若该key已存在(即 key-value已存在 ),则用 新value 替换 旧value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue; //并返回旧的value
                }
            }
    
            modCount++;
    
    (分析5)// 3.2 若 该key不存在,则将“key-value”添加到table中
            addEntry(hash, key, value, i);
            return null;
        }
    
    • 根据源码分析所作出的流程图

    示意图

    • 下面,我将根据上述流程的5个分析点进行详细讲解

    分析1:初始化哈希表

    即 初始化数组(table)、扩容阈值(threshold

       /**
         * 函数使用原型
         */
          if (table == EMPTY_TABLE) { 
            inflateTable(threshold); 
        }  
    
       /**
         * 源码分析:inflateTable(threshold); 
         */
         private void inflateTable(int toSize) {  
        
        // 1. 将传入的容量大小转化为:>传入容量大小的最小的2的次幂
        // 即如果传入的是容量大小是19,那么转化后,初始化容量大小为32(即2的5次幂)
        int capacity = roundUpToPowerOf2(toSize);->>分析1   
    
        // 2. 重新计算阈值 threshold = 容量 * 加载因子  
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  
    
        // 3. 使用计算后的初始容量(已经是2的次幂) 初始化数组table(作为数组长度)
        // 即 哈希表的容量大小 = 数组大小(长度)
        table = new Entry[capacity]; //用该容量初始化table  
    
        initHashSeedAsNeeded(capacity);  
    }  
    
        /**
         * 分析1:roundUpToPowerOf2(toSize)
         * 作用:将传入的容量大小转化为:>传入容量大小的最小的2的幂
         * 特别注意:容量大小必须为2的幂,该原因在下面的讲解会详细分析
         */
    
         private static int roundUpToPowerOf2(int number) {  
       
           //若 容量超过了最大值,初始化容量设置为最大值 ;否则,设置为:>传入容量大小的最小的2的次幂
           return number >= MAXIMUM_CAPACITY  ? 
                MAXIMUM_CAPACITY  : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  
    
    • 再次强调:真正初始化哈希表(初始化存储数组table)是在第1次添加键值对时,即第1次调用put()

    分析2:当 key ==null时,将该 key-value 的存储位置规定为数组table 中的第1个位置,即table [0]

       /**
         * 函数使用原型
         */
          if (key == null)
               return putForNullKey(value);
    
       /**
         * 源码分析:putForNullKey(value)
         */
          private V putForNullKey(V value) {  
            // 遍历以table[0]为首的链表,寻找是否存在key==null 对应的键值对
            // 1. 若有:则用新value 替换 旧value;同时返回旧的value值
            for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
              if (e.key == null) {   
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
    
        // 2 .若无key==null的键,那么调用addEntry(),将空键 & 对应的值封装到Entry中,并放到table[0]中
        addEntry(0, null, value, 0); 
        // 注:
        // a. addEntry()的第1个参数 = hash值 = 传入0
        // b. 即 说明:当key = null时,也有hash值 = 0,所以HashMap的key 可为null
        // c. 对比HashTable,由于HashTable对key直接hashCode(),若key为null时,会抛出异常,所以HashTable的key不可为null
        // d. 此处只需知道是将 key-value 添加到HashMap中即可,关于addEntry()的源码分析将等到下面再详细说明,
        return null;  
    
    }     
    

    从此处可以看出:

    • HashMap的键key 可为null(区别于 HashTablekey 不可为null
    • HashMap的键key 可为null且只能为1个,但值value可为null且为多个

    分析3:计算存放数组 table 中的位置(即 数组下标 or 索引)

       /**
         * 函数使用原型
         * 主要分为2步:计算hash值、根据hash值再计算得出最后数组位置
         */
            // a. 根据键值key计算hash值 ->> 分析1
            int hash = hash(key);
            // b. 根据hash值 最终获得 key对应存放的数组Table中位置 ->> 分析2
            int i = indexFor(hash, table.length);
    
       /**
         * 源码分析1:hash(key)
         * 该函数在JDK 1.7 和 1.8 中的实现不同,但原理一样 = 扰动函数 = 使得根据key生成的哈希码(hash值)分布更加均匀、更具备随机性,避免出现hash值冲突(即指不同key但生成同1个hash值)
         * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
         * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
         */
    
         // JDK 1.7实现:将 键key 转换成 哈希码(hash值)操作  = 使用hashCode() + 4次位运算 + 5次异或运算(9次扰动)
         static final int hash(int h) {
            h ^= k.hashCode(); 
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
         }
    
          // JDK 1.8实现:将 键key 转换成 哈希码(hash值)操作 = 使用hashCode() + 1次位运算 + 1次异或运算(2次扰动)
          // 1. 取hashCode值: h = key.hashCode() 
         //  2. 高位参与低位的运算:h ^ (h >>> 16)  
          static final int hash(Object key) {
               int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
                // a. 当key = null时,hash值 = 0,所以HashMap的key 可为null      
                // 注:对比HashTable,HashTable对key直接hashCode(),若key为null时,会抛出异常,所以HashTable的key不可为null
                // b. 当key ≠ null时,则通过先计算出 key的 hashCode()(记为h),然后 对哈希码进行 扰动处理: 按位 异或(^) 哈希码自身右移16位后的二进制
         }
    
       /**
         * 函数源码分析2:indexFor(hash, table.length)
         * JDK 1.8中实际上无该函数,但原理相同,即具备类似作用的函数
         */
          static int indexFor(int h, int length) {  
              return h & (length-1); 
              // 将对哈希码扰动处理后的结果 与运算(&) (数组长度-1),最终得到存储在数组table的位置(即数组下标、索引)
    }
    
    • 总结 计算存放在数组 table 中的位置(即数组下标、索引)的过程
      示意图

    在了解 如何计算存放数组table 中的位置 后,所谓 知其然 而 需知其所以然,下面我将讲解为什么要这样计算,即主要解答以下3个问题:

    1. 为什么不直接采用经过hashCode()处理的哈希码 作为 存储数组table的下标位置?
    2. 为什么采用 哈希码 与运算(&) (数组长度-1) 计算数组下标?
    3. 为什么在计算数组下标前,需对哈希码进行二次处理:扰动处理?

    在回答这3个问题前,请大家记住一个核心思想:

    所有处理的根本目的,都是为了提高 存储key-value的数组下标位置 的随机性 & 分布均匀性,尽量避免出现hash值冲突。即:对于不同key,存储的数组下标位置要尽可能不一样

    问题1:为什么不直接采用经过hashCode()处理的哈希码 作为 存储数组table的下标位置?

    • 结论:容易出现 哈希码 与 数组大小范围不匹配的情况,即 计算出来的哈希码可能 不在数组大小范围内,从而导致无法匹配存储位置
    • 原因描述

    示意图

    • 为了解决 “哈希码与数组大小范围不匹配” 的问题,HashMap给出了解决方案:哈希码 与运算(&) (数组长度-1);请继续问题2

    问题2:为什么采用 哈希码 与运算(&) (数组长度-1) 计算数组下标?

    • 结论:根据HashMap的容量大小(数组长度),按需取 哈希码一定数量的低位 作为存储的数组下标位置,从而 解决 “哈希码与数组大小范围不匹配” 的问题

    • 具体解决方案描述

    示意图

    问题3:为什么在计算数组下标前,需对哈希码进行二次处理:扰动处理?

    • 结论:加大哈希码低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性 & 均匀性,最终减少Hash冲突

    • 具体描述

    示意图

    至此,关于怎么计算 key-value 值存储在HashMap数组位置 & 为什么要这么计算,讲解完毕。


    分析4:若对应的key已存在,则 使用 新value 替换 旧value

    注:当发生 Hash冲突时,为了保证 键key的唯一性哈希表并不会马上在链表中插入新数据,而是先查找该 key是否已存在,若已存在,则替换即可

       /**
         * 函数使用原型
         */
    // 2. 判断该key对应的值是否已存在(通过遍历 以该数组元素为头结点的链表 逐个判断)
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                // 2.1 若该key已存在(即 key-value已存在 ),则用 新value 替换 旧value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue; //并返回旧的value
                }
            }
    
            modCount++;
    
            // 2.2 若 该key不存在,则将“key-value”添加到table中
            addEntry(hash, key, value, i);
            return null;
    
    • 此处无复杂的源码分析,但此处的分析点主要有2个:替换流程 & key是否存在(即key值的对比)

    分析1:替换流程

    具体如下图:
    示意图

    分析2:key值的比较

    采用 equals() 或 “==” 进行比较,下面给出其介绍 & 与 “==”使用的对比
    示意图


    分析5:若对应的key不存在,则将该“key-value”添加到数组table的对应位置中

    • 函数源码分析如下
          /**
            * 函数使用原型
            */
           // 2. 判断该key对应的值是否已存在
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                // 2.1 若该key对应的值已存在,则用新的value取代旧的value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this); 
                    return oldValue; 
                }
            }
    
            modCount++;
    
            // 2.2 若 该key对应的值不存在,则将“key-value”添加到table中
            addEntry(hash, key, value, i);
    
       /**
         * 源码分析:addEntry(hash, key, value, i)
         * 作用:添加键值对(Entry )到 HashMap中
         */
          void addEntry(int hash, K key, V value, int bucketIndex) {  
              // 参数3 = 插入数组table的索引位置 = 数组下标
              
              // 1. 插入前,先判断容量是否足够
              // 1.1 若不足够,则进行扩容(2倍)、重新计算Hash值、重新计算存储数组下标
              if ((size >= threshold) && (null != table[bucketIndex])) {  
                resize(2 * table.length); // a. 扩容2倍  --> 分析1
                hash = (null != key) ? hash(key) : 0;  // b. 重新计算该Key对应的hash值
                bucketIndex = indexFor(hash, table.length);  // c. 重新计算该Key对应的hash值的存储数组下标位置
        }  
    
        // 1.2 若容量足够,则创建1个新的数组元素(Entry) 并放入到数组中--> 分析2
        createEntry(hash, key, value, bucketIndex);  
    }  
    
     /**
       * 分析1:resize(2 * table.length)
       * 作用:当容量不足时(容量 > 阈值),则扩容(扩到2倍)
       */ 
       void resize(int newCapacity) {  
        
        // 1. 保存旧数组(old table) 
        Entry[] oldTable = table;  
    
        // 2. 保存旧容量(old capacity ),即数组长度
        int oldCapacity = oldTable.length; 
    
        // 3. 若旧容量已经是系统默认最大容量了,那么将阈值设置成整型的最大值,退出    
        if (oldCapacity == MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;  
            return;  
        }  
      
        // 4. 根据新容量(2倍容量)新建1个数组,即新table  
        Entry[] newTable = new Entry[newCapacity];  
    
        // 5. 将旧数组上的数据(键值对)转移到新table中,从而完成扩容 ->>分析1.1 
        transfer(newTable); 
    
        // 6. 新数组table引用到HashMap的table属性上
        table = newTable;  
    
        // 7. 重新设置阈值  
        threshold = (int)(newCapacity * loadFactor); 
    } 
    
     /**
       * 分析1.1:transfer(newTable); 
       * 作用:将旧数组上的数据(键值对)转移到新table中,从而完成扩容
       * 过程:按旧链表的正序遍历链表、在新链表的头部依次插入
       */ 
    void transfer(Entry[] newTable) {
          // 1. src引用了旧数组
          Entry[] src = table; 
    
          // 2. 获取新数组的大小 = 获取新容量大小                 
          int newCapacity = newTable.length;
    
          // 3. 通过遍历 旧数组,将旧数组上的数据(键值对)转移到新数组中
          for (int j = 0; j < src.length; j++) { 
          	  // 3.1 取得旧数组的每个元素  
              Entry<K,V> e = src[j];           
              if (e != null) {
                  // 3.2 释放旧数组的对象引用(for循环后,旧数组不再引用任何对象)
                  src[j] = null; 
    
                  do { 
                      // 3.3 遍历 以该数组元素为首 的链表
                      // 注:转移链表时,因是单链表,故要保存下1个结点,否则转移后链表会断开
                      Entry<K,V> next = e.next; 
                     // 3.4 重新计算每个元素的存储位置
                     int i = indexFor(e.hash, newCapacity); 
                     // 3.5 将元素放在数组上:采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
                     // 即 扩容后,可能出现逆序:按旧链表的正序遍历链表、在新链表的头部依次插入
                     e.next = newTable[i]; 
                     newTable[i] = e;  
                     // 3.6 访问下1个Entry链上的元素,如此不断循环,直到遍历完该链表上的所有节点
                     e = next;             
                 } while (e != null);
                 // 如此不断循环,直到遍历完数组上的所有数据元素
             }
         }
     }
    
     /**
       * 分析2:createEntry(hash, key, value, bucketIndex);  
       * 作用: 若容量足够,则创建1个新的数组元素(Entry) 并放入到数组中
       */  
    void createEntry(int hash, K key, V value, int bucketIndex) { 
    
        // 1. 把table中该位置原来的Entry保存  
        Entry<K,V> e = table[bucketIndex];
    
        // 2. 在table中该位置新建一个Entry:将原头结点位置(数组上)的键值对 放入到(链表)后1个节点中、将需插入的键值对 放入到头结点中(数组上)-> 从而形成链表
        // 即 在插入元素时,是在链表头插入的,table中的每个位置永远只保存最新插入的Entry,旧的Entry则放入到链表中(即 解决Hash冲突)
        table[bucketIndex] = new Entry<>(hash, key, value, e);  
    
        // 3. 哈希表的键值对数量计数增加
        size++;  
    }   
    

    此处有2点需特别注意:键值对的添加方式 & 扩容机制

    1. 键值对的添加方式:单链表的头插法

    • 即 将该位置(数组上)原来的数据放在该位置的(链表)下1个节点中(next)、在该位置(数组上)放入需插入的数据-> 从而形成链表
    • 如下示意图

    示意图

    2. 扩容机制

    • 具体流程如下:

    示意图

    • 扩容过程中的转移数据示意图如下

    示意图

    在扩容resize()过程中,在将旧数组上的数据 转移到 新数组上时,转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入,即在转移数据、扩容后,容易出现链表逆序的情况

    设重新计算存储位置后不变,即扩容前 = 1->2->3,扩容后 = 3->2->1

    • 此时若(多线程)并发执行 put()操作,一旦出现扩容情况,则 容易出现 环形链表,从而在获取数据、遍历链表时 形成死循环(Infinite Loop),即 死锁的状态 = 线程不安全

    下面最后1节会对上述情况详细说明

    总结

    • HashMap 添加数据(成对 放入 键 - 值对)的全流程

    示意图

    • 示意图
      示意图

    至此,关于 “向 HashMap 添加数据(成对 放入 键 - 值对)“讲解完毕


    步骤3:从HashMap中获取数据

    • 假如理解了上述put()函数的原理,那么get()函数非常好理解,因为二者的过程原理几乎相同
    • get()函数的流程如下:

    示意图

    • 具体源码分析如下
    /**
       * 函数原型
       * 作用:根据键key,向HashMap获取对应的值
       */ 
       map.get(key);
    
    
     /**
       * 源码分析
       */ 
       public V get(Object key) {  
    
        // 1. 当key == null时,则到 以哈希表数组中的第1个元素(即table[0])为头结点的链表去寻找对应 key == null的键
        if (key == null)  
            return getForNullKey(); --> 分析1
    
        // 2. 当key ≠ null时,去获得对应值 -->分析2
        Entry<K,V> entry = getEntry(key);
      
        return null == entry ? null : entry.getValue();  
    }  
    
    
     /**
       * 分析1:getForNullKey()
       * 作用:当key == null时,则到 以哈希表数组中的第1个元素(即table[0])为头结点的链表去寻找对应 key == null的键
       */ 
    private V getForNullKey() {  
    
        if (size == 0) {  
            return null;  
        }  
    
        // 遍历以table[0]为头结点的链表,寻找 key==null 对应的值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
    
            // 从table[0]中取key==null的value值 
            if (e.key == null)  
                return e.value; 
        }  
        return null;  
    }  
     
     /**
       * 分析2:getEntry(key)
       * 作用:当key ≠ null时,去获得对应值
       */  
    final Entry<K,V> getEntry(Object key) {  
    
        if (size == 0) {  
            return null;  
        }  
    
        // 1. 根据key值,通过hash()计算出对应的hash值
        int hash = (key == null) ? 0 : hash(key);  
    
        // 2. 根据hash值计算出对应的数组下标
        // 3. 遍历 以该数组下标的数组元素为头结点的链表所有节点,寻找该key对应的值
        for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  
    
            Object k;  
            // 若 hash值 & key 相等,则证明该Entry = 我们要的键值对
            // 通过equals()判断key是否相等
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k))))  
                return e;  
        }  
        return null;  
    }  
    

    至此,关于 “向 HashMap 获取数据 “讲解完毕


    步骤4:对HashMap的其他操作

    即 对其余使用API(函数、方法)的源码分析

    • HashMap除了核心的put()get()函数,还有以下主要使用的函数方法
    void clear(); // 清除哈希表中的所有键值对
    int size();  // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
    boolean isEmpty(); // 判断HashMap是否为空;size == 0时 表示为 空 
    
    void putAll(Map<? extends K, ? extends V> m);  // 将指定Map中的键值对 复制到 此Map中
    V remove(Object key);  // 删除该键值对
    
    boolean containsKey(Object key); // 判断是否存在该键的键值对;是 则返回true
    boolean containsValue(Object value);  // 判断是否存在该值的键值对;是 则返回true
     
    
    • 下面将简单介绍上面几个函数的源码分析
      /**
       * 函数:isEmpty()
       * 作用:判断HashMap是否为空,即无键值对;size == 0时 表示为 空 
       */
    
    public boolean isEmpty() {  
        return size == 0;  
    } 
    
     /**
       * 函数:size()
       * 作用:返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
       */
    
       public int size() {  
        return size;  
    }  
    
     /**
       * 函数:clear()
       * 作用:清空哈希表,即删除所有键值对
       * 原理:将数组table中存储的Entry全部置为null、size置为0
       */ 
    public void clear() {  
        modCount++;  
        Arrays.fill(table, null);
        size = 0;
    }  
    
    /**
       * 函数:putAll(Map<? extends K, ? extends V> m)
       * 作用:将指定Map中的键值对 复制到 此Map中
       * 原理:类似Put函数
       */ 
    
        public void putAll(Map<? extends K, ? extends V> m) {  
        // 1. 统计需复制多少个键值对  
        int numKeysToBeAdded = m.size();  
        if (numKeysToBeAdded == 0)  
            return; 
    
        // 2. 若table还没初始化,先用刚刚统计的复制数去初始化table  
        if (table == EMPTY_TABLE) {  
            inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));  
        }  
      
        // 3. 若需复制的数目 > 阈值,则需先扩容 
        if (numKeysToBeAdded > threshold) {  
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);  
            if (targetCapacity > MAXIMUM_CAPACITY)  
                targetCapacity = MAXIMUM_CAPACITY;  
            int newCapacity = table.length;  
            while (newCapacity < targetCapacity)  
                newCapacity <<= 1;  
            if (newCapacity > table.length)  
                resize(newCapacity);  
        }  
        // 4. 开始复制(实际上不断调用Put函数插入)  
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
            put(e.getKey(), e.getValue());
    }  
    
     /**
       * 函数:remove(Object key)
       * 作用:删除该键值对
       */ 
    
    public V remove(Object key) {  
        Entry<K,V> e = removeEntryForKey(key);  
        return (e == null ? null : e.value);  
    }  
      
    final Entry<K,V> removeEntryForKey(Object key) {  
        if (size == 0) {  
            return null;  
        }  
        // 1. 计算hash值
        int hash = (key == null) ? 0 : hash(key);  
        // 2. 计算存储的数组下标位置
        int i = indexFor(hash, table.length);  
        Entry<K,V> prev = table[i];  
        Entry<K,V> e = prev;  
      
        while (e != null) {  
            Entry<K,V> next = e.next;  
            Object k;  
            if (e.hash == hash &&  
                ((k = e.key) == key || (key != null && key.equals(k)))) {  
                modCount++;  
                size--; 
                // 若删除的是table数组中的元素(即链表的头结点) 
                // 则删除操作 = 将头结点的next引用存入table[i]中  
                if (prev == e) 
                    table[i] = next;
    
                //否则 将以table[i]为头结点的链表中,当前Entry的前1个Entry中的next 设置为 当前Entry的next(即删除当前Entry = 直接跳过当前Entry)
                else  
                    prev.next = next;   
                e.recordRemoval(this);  
                return e;  
            }  
            prev = e;  
            e = next;  
        }  
      
        return e;  
    } 
    
     /**
       * 函数:containsKey(Object key)
       * 作用:判断是否存在该键的键值对;是 则返回true
       * 原理:调用get(),判断是否为Null
       */
       public boolean containsKey(Object key) {  
        return getEntry(key) != null; 
    } 
    
     /**
       * 函数:containsValue(Object value)
       * 作用:判断是否存在该值的键值对;是 则返回true
       */   
    public boolean containsValue(Object value) {  
        // 若value为空,则调用containsNullValue()  
        if (value == null)
            return containsNullValue();  
        
        // 若value不为空,则遍历链表中的每个Entry,通过equals()比较values 判断是否存在
        Entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)  
            for (Entry e = tab[i] ; e != null ; e = e.next)  
                if (value.equals(e.value)) 
                    return true;//返回true  
        return false;  
    }  
      
    // value为空时调用的方法  
    private boolean containsNullValue() {  
        Entry[] tab = table;  
        for (int i = 0; i < tab.length ; i++)  
            for (Entry e = tab[i] ; e != null ; e = e.next)  
                if (e.value == null)
                    return true;  
        return false;  
    } 
    
    

    至此,关于HashMap的底层原理 & 主要使用API(函数、方法)讲解完毕。


    6. 源码总结

    下面,用3个图总结整个源码内容:

    总结内容 = 数据结构、主要参数、添加 & 查询数据流程、扩容机制

    • 数据结构 & 主要参数
      示意图

    • 添加 & 查询数据流程
      示意图

    • 扩容机制
      示意图


    7. 与 JDK 1.8的区别

    HashMap 的实现在 JDK 1.7JDK 1.8 差别较大,具体区别如下

    JDK 1.8 的优化目的主要是:减少 Hash冲突 & 提高哈希表的存、取效率;关于 JDK 1.8HashMap 的源码解析请看文章:Java源码分析:关于 HashMap 1.8 的重大更新

    7.1 数据结构

    示意图

    7.2 获取数据时(获取数据 类似)

    示意图

    7.3 扩容机制

    示意图


    8. 额外补充:关于HashMap的其他问题

    • 有几个小问题需要在此补充

    示意图

    • 具体如下

    8.1 哈希表如何解决Hash冲突

    示意图

    8.2 为什么HashMap具备下述特点:键-值(key-value)都允许为空、线程不安全、不保证有序、存储位置随时间变化

    • 具体解答如下

    示意图

    • 下面主要讲解 HashMap 线程不安全的其中一个重要原因:多线程下容易出现resize()死循环
      本质 = 并发 执行 put()操作导致触发 扩容行为,从而导致 环形链表,使得在获取数据遍历链表时形成死循环,即Infinite Loop

    • 先看扩容的源码分析resize()

    关于resize()的源码分析已在上文详细分析,此处仅作重点分析:transfer()

    /**
       * 源码分析:resize(2 * table.length)
       * 作用:当容量不足时(容量 > 阈值),则扩容(扩到2倍)
       */ 
       void resize(int newCapacity) {  
        
        // 1. 保存旧数组(old table) 
        Entry[] oldTable = table;  
    
        // 2. 保存旧容量(old capacity ),即数组长度
        int oldCapacity = oldTable.length; 
    
        // 3. 若旧容量已经是系统默认最大容量了,那么将阈值设置成整型的最大值,退出    
        if (oldCapacity == MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;  
            return;  
        }  
      
        // 4. 根据新容量(2倍容量)新建1个数组,即新table  
        Entry[] newTable = new Entry[newCapacity];  
    
        // 5. (重点分析)将旧数组上的数据(键值对)转移到新table中,从而完成扩容 ->>分析1.1 
        transfer(newTable); 
    
        // 6. 新数组table引用到HashMap的table属性上
        table = newTable;  
    
        // 7. 重新设置阈值  
        threshold = (int)(newCapacity * loadFactor); 
    } 
    
     /**
       * 分析1.1:transfer(newTable); 
       * 作用:将旧数组上的数据(键值对)转移到新table中,从而完成扩容
       * 过程:按旧链表的正序遍历链表、在新链表的头部依次插入
       */ 
    void transfer(Entry[] newTable) {
          // 1. src引用了旧数组
          Entry[] src = table; 
    
          // 2. 获取新数组的大小 = 获取新容量大小                 
          int newCapacity = newTable.length;
    
          // 3. 通过遍历 旧数组,将旧数组上的数据(键值对)转移到新数组中
          for (int j = 0; j < src.length; j++) { 
              // 3.1 取得旧数组的每个元素  
              Entry<K,V> e = src[j];           
              if (e != null) {
                  // 3.2 释放旧数组的对象引用(for循环后,旧数组不再引用任何对象)
                  src[j] = null; 
    
                  do { 
                      // 3.3 遍历 以该数组元素为首 的链表
                      // 注:转移链表时,因是单链表,故要保存下1个结点,否则转移后链表会断开
                      Entry<K,V> next = e.next; 
                     // 3.3 重新计算每个元素的存储位置
                     int i = indexFor(e.hash, newCapacity); 
                     // 3.4 将元素放在数组上:采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
                     // 即 扩容后,可能出现逆序:按旧链表的正序遍历链表、在新链表的头部依次插入
                     e.next = newTable[i]; 
                     newTable[i] = e;  
                     // 访问下1个Entry链上的元素,如此不断循环,直到遍历完该链表上的所有节点
                     e = next;             
                 } while (e != null);
                 // 如此不断循环,直到遍历完数组上的所有数据元素
             }
         }
     }
    

    从上面可看出:在扩容resize()过程中,在将旧数组上的数据 转移到 新数组上时,转移数据操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入,即在转移数据、扩容后,容易出现链表逆序的情况

    设重新计算存储位置后不变,即扩容前 = 1->2->3,扩容后 = 3->2->1

    • 此时若(多线程)并发执行 put()操作,一旦出现扩容情况,则 容易出现 环形链表,从而在获取数据、遍历链表时 形成死循环(Infinite Loop),即 死锁的状态,具体请看下图:

    初始状态、步骤1、步骤2

    示意图

    示意图

    示意图

    注:由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入,所以不会出现链表 逆序、倒置的情况,故不容易出现环形链表的情况。

    JDK 1.8 还是线程不安全,因为 无加同步锁保护

    8.3 为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

    示意图

    8.4 HashMap 中的 keyObject类型, 则需实现哪些方法?

    示意图

    至此,关于HashMap的所有知识讲解完毕。


    9. 总结

    • 本文主要讲解 JavaHashMap源码 & 相关知识
    • 下面我将继续对 Android & Java中的知识进行深入讲解 ,感兴趣的同学可以继续关注 CSDN博客 与 微信公众号。

    请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

    展开全文
  • 源码分析RocketMQ系列索引

    万次阅读 多人点赞 2017-12-24 23:01:08
    1、RocketMQ源码分析之NameServer 2、RocketMQ源码分析之Broker概述与同步消息发送原理与高可用设计及思考 3、源码分析RocketMQ之CommitLog消息存储机制 4、源码分析RocketMQ之消息消费 5、源码分析RocketMQ消息...

    1、RocketMQ源码分析之NameServer

    2、RocketMQ源码分析之Broker概述与同步消息发送原理与高可用设计及思考

    3、源码分析RocketMQ之CommitLog消息存储机制

    4、源码分析RocketMQ之消息消费

    5、源码分析RocketMQ消息消费机制----消费者拉取消息机制

    6、 源码分析RocketMQ消息消费机制----消费端消息负载均衡机制与重新分布

    7、源码分析RocketMQ消息重试机制

    8、源码分析RocketMQ消费ACK机制之消息进度

    9、源码分析RocketMQ之消费队列、Index索引文件存储结构与存储机制-上篇

    10、 源码分析RocketMQ之消费队列、Index索引文件存储结构与存储机制-下篇

    11、源码分析RocketMQ刷盘机制

    12、源码分析RocketMQ消息过滤机制上篇-----消息消费服务端过滤与TAG模式过滤实现

    13、源码分析RocketMQ消息过滤机制下篇-FilterServer、ClassFilter模式详解

    14、源码分析RocketMQ拉模式

    15、源码分析RocketMQ长轮询机制

    16、源码分析RocketMQ顺序消息消费实现原理

    17、源码分析RocketMQ文件过期删除机制

    18、源码研究RocketMQ高可用HA机制

    19、源码研究RocketMQ读写分离机制

    20、RocketMQ源码分析之从官方示例窥探RocketMQ事务消息实现基本思想

    21、RocketMQ源码分析之RocketMQ事务消息实现原理上篇

    22、RocketMQ源码分析之RocketMQ事务消息实现原理中篇----事务消息状态回查

    23、RocketMQ源码分析之事务消息实现原理下篇-消息服务器Broker提交回滚事务实现原理

    24、RocketMQ事务消息实战

    25、RocketMQ实战:生产环境中,autoCreateTopicEnable为什么不能设置为true

    26、RocketMQ 消息发送system busy、broker busy原因分析与解决方案

    27、RocketMQ HA机制(主从同步)

    28、RocketMQ ACL使用指南

    29、源码分析RocketMQ ACL实现机制

    30、RocketMQ消息轨迹-设计篇

    31、源码分析RocketMQ消息轨迹

    32、RocketMQ一个新的消费组初次启动时从何处开始消费呢?

    33、RocketMQ 多副本前置篇:初探raft协议

    34、源码分析 RocketMQ DLedger 多副本之 Leader 选主

    35、源码分析 RocketMQ DLedger 多副本存储实现

    36、RocketMQ 主题扩分片后遇到的坑

    37、源码分析 RocketMQ DLedger(多副本) 之日志追加流程

    38、源码分析 RocketMQ DLedger(多副本) 之日志复制(传播)

    39、基于 raft 协议的 RocketMQ DLedger 多副本日志复制设计原理

    40、RocketMQ 整合 DLedger(多副本)即主从切换实现平滑升级的设计技巧

    41、源码分析 RocketMQ DLedger 多副本即主从切换实现原理

    42、RocketMQ 升级到主从切换(实战篇)

     

    更多文章请关注作者微信公众号:

    博客作者的新书《RocketMQ技术内幕》已出版上市了,目前可在主流购物平台(京东、天猫等)购买。

    本书从源码角度深度分析了RocketMQ NameServer、消息发送、消息存储、消息消费、消息过滤、主从同步HA、事务消息;在实战篇重点介绍了RocketMQ运维管理界面与当前支持的39个运维命令;并在附录部分罗列了RocketMQ几乎所有的配置参数。本书得到了RocketMQ创始人、阿里巴巴Messaging开源技术负责人、Linux OpenMessaging 主席的高度认可并作序推荐。目前是国内第一本成体系剖析RocketMQ的书籍。 
     

     

     

    展开全文
  • spring系列源码分析

    2019-01-28 23:10:19
    spring系列源码分析
  • Hadoop源码分析 完整版 共55章

    千次下载 热门讨论 2011-07-26 22:41:27
    caibinbupt的Hadoop源码分析完整版,包括 HDFS 和 MapReduce。 HDFS: 41章 MapReduce: 14章
  • Stack源码分析

    万次阅读 2021-03-02 14:15:26
    文章目录概述源码分析总结 源码分析 代码如下(示例): public class Stack<E> extends Vector<E> { /** * 无参数构造器 */ public Stack() { } /** * 压栈操作,往栈顶插入。其实就是插入...

    概述

    Stack是栈结构,继承Vector。具体的实现是数组。



    源码分析

    代码如下(示例):

    public
    class Stack<E> extends Vector<E> {
        /**
         * 无参数构造器
         */
        public Stack() {
        }
    
        /**
         * 压栈操作,往栈顶插入。其实就是插入数组的尾部
         */
        public E push(E item) {
            addElement(item);
            return item;
        }
    
        /**
         * 弹栈操作。也就是删除栈顶元素。其实就是删除数组的最后一个元素
         */
        public synchronized E pop() {
            E       obj;
            int     len = size();
    
            obj = peek();
            removeElementAt(len - 1);
    
            return obj;
        }
    
        /**
         *  查找栈顶元素
         */
        public synchronized E peek() {
            int     len = size();
    
            if (len == 0)
                throw new EmptyStackException();
            return elementAt(len - 1);
        }
    
        /**
         * 判断是否为空
         */
        public boolean empty() {
            return size() == 0;
        }
    
        /**
         * 查询元素
         */
        public synchronized int search(Object o) {
            int i = lastIndexOf(o);
    
            if (i >= 0) {
                return size() - i;
            }
            return -1;
        }
    
    }
    
    

    总结

    1 所有的方法都是同步方法
    2 继承Vector。API的实现都调用了父类的方法
    3 属于历史容器

    展开全文
  • 以太坊源码分析

    2019-12-12 12:36:29
    本节为以太坊源码分析,主要通过对以太坊源码的讲解,来进一步加强对以太坊相关知识的掌握。
  • mybatis源码分析

    万次阅读 2019-08-05 08:41:01
    spring和mybatis源码分析 mybatis的流程分析 在整合spring的情况下,mybatis从哪里开始 首先分析得知mybatis和spring整合的情况下,主要是提供两处关联 @MapperScan @Bean---->SqlSessionFactoryBean 通过源码...
  • 源码分析Sentinel专栏

    千次阅读 2020-05-08 20:53:13
    源码分析Sentinel系列是打造的又一重磅专题,详细介绍了限流、熔断的实现原理。 1、Alibaba Sentinel 限流与熔断初探(技巧篇) 2、源码分析 Sentinel 之 Dubbo 适配原理 3、源码分析 Alibaba sentinel 滑动窗口实现...
  • FBReader源码分析

    热门讨论 2014-10-20 23:16:36
    FBReader源码分析,共五章。基于FBReader1.0版本
  • leveldb源码分析

    热门讨论 2013-12-04 15:10:14
    leveldb源码分析
  • BERT源码分析

    千次阅读 2019-07-06 19:08:50
    BERT源码分析PART I BERT源码分析PART II BERT源码分析PART III
  • Docker源码分析

    千次下载 热门讨论 2015-07-29 15:09:57
    国内一部Docker源码分析著作;从源码角度全面解析Docker设计与实现;填补Docker理论与实践之间的鸿沟
  • 提示:本文基于开源鸿蒙内核分析,官方源码【kernel_liteos_a】,官方文档【docs】...鸿蒙内核源码分析(Task/线程管理篇) 鸿蒙内核源码分析(进程管理篇) 鸿蒙内核源码分析(调度队列篇) 以便对本文任务调度机制的理解
  • 源码分析Dubbo系列文章

    万次阅读 多人点赞 2018-06-09 22:57:09
    本系列文章主要针对Dubbo2.6.2(dubbox2.8.4)版本,从源码的角度分析Dubbo内部的实现细节,加深对Dubbo的...2、源码分析Dubbo服务提供者启动流程-上篇 3、源码分析Dubbo服务提供者启动流程-下篇 4、源码分析Dubb...
  • springIOC底层源码分析

    2019-05-15 14:25:03
    本课程来自鲁班学院Java架构师VIP课程中框架源码专题中springIOC源码分析中的部分内
  • Zookeeper源码分析

    2012-03-04 11:54:40
    zookeeper源码分析(一)工作原理概述 zookeeper源码分析(二)FastLeader选举算法 Zookeeper源码分析之Paxos算法之旅
  • 本系列全部文章进入鸿蒙系统源码分析(总目录)查看 前言:因笔者在大学有痛苦阅读linux0.11内核的经历,所以一直有个心结,在很多同学眼中操作系统内核运作是神秘莫测的,一直想让更多人能明白其内在机制,甚至让一...
  • ANDROID源码分析实录

    热门讨论 2016-01-11 09:52:11
    《Android源码分析实录》共分为15章,主要内容包括走进Android世界、硬件抽象层详解、分析JNI(Java本地接口)层、Android内存系统分析、Andmid虚拟机系统详解、IPC通信机制详解、Zygote进程/System进程和应用程序...
  • redis源码分析

    万次阅读 2019-12-25 13:54:48
    参考文献: redis源码分析:CSDN 如何高效深入的阅读Redis的源码?知乎 Redis源码从哪里读起? Redis google code Download
  • package com.sol.springframework.service; import com.sol.springframework.pojo.LoginUser; /** * @author: lujie * @create: 2020/3/24 * @description: LoginService ...public interface LoginService { ...}
  • 源码分析Mybatis专栏

    千次阅读 2019-07-28 09:51:03
    源码分析Mybatis专栏,目前重点关注Mybatis的初始化流程、SQL执行流程、Mybatis扩展机制与缓存机制。创作背景是我在落地公司全链路压测系统时,调研数据库层面的数据隔离方案时做的一些技术研究。 1、源码分析...
  • Etcd源码分析之clientv3源码分析(1)

    千次阅读 2018-03-04 23:58:36
    Etcd源码分析之clientv3源码分析(1) etcd是用于共享配置和服务发现的分布式,一致性的KV存储系统,使用Go语言实现。 目前在工作中接触到这个软件,顺便对其部门源码进行了一些分析,现整理总结博客中。 Etcd...
  • 提示:本文为鸿蒙系统源码分析总目录,源码来自官方源码库【OpenHarmony】,项目来自【开放原子开源基金会】 本文作者:鸿蒙生态发烧友,将持续研究鸿蒙系统源码,敬请关注。内容仅代表个人观点,错误之处,欢迎大家...
  • spring源码分析

    千次阅读 多人点赞 2018-08-17 02:51:18
    1、spring ioc源码分析   Spring IOC中bean的创建是利用反射+xml解析实现的,因此这里也围绕这个来做分析。 ClassPathXmlApplicationContext applicationContext=new ClassPathXmlApplicationContext("...
  • lighttpd源码分析

    热门讨论 2009-10-28 14:28:44
    各基本数据结构的分析整理 lighttpd源码最核心的东西(比如配置信息的加载 比如对客户请求访问的响应 等)很齐全的源码分析资料,是掌握反向代理的好东东,后续敬请期待,不断推出中
  • Nginx源码分析(25篇)

    万次阅读 多人点赞 2018-09-19 19:36:17
    Nginx源码分析 - 初探Nginx的架构 Nginx源码分析 - 基础数据结构篇 - 内存池 ngx_palloc.c Nginx源码分析 - 基础数据结构篇 - 数组结构 ngx_array.c Nginx源码分析 - 基础数据结构篇 - 缓冲区结构 ngx_buf.c ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 950,145
精华内容 380,058
关键字:

源码分析