精华内容
下载资源
问答
  • 下面通过存储与获取数据的过程介绍字典的底层原理。 存储数据的过程 例如,我们将‘name’ = ‘张三’ 这个键值对存储到字典map中,假设数组长度为8,可以用3位二进制表示。 >>> map = {} >>> map {} >>> map['...
  • HashMap底层原理

    2019-09-28 11:52:32
    HashMap底层原理
  • KVC,KVO,Category,load.initalize,关联对象,关联对象,OC对象本质,事件的产生传递及响应,block底层研究
  • SpringCloud底层原理

    2021-02-24 22:20:58
    不过大多数讲解还停留在对SpringCloud功能使用的层面,其底层的很多原理,很多人可能并不知晓。实际上,SpringCloud是一个全家桶式的技术栈,它包含了很多组件。本文先从最核心的几个组件,也就是Eureka、Ribbon、...
  • 主要介绍了通过实例解析JMM和Volatile底层原理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 《大话存储2:存储系统架构与底层原理极限剖析》适合初入存储行业的研发人员、技术工程师、售前工程师和销售人员阅读,同时适合资深存储行业人士用以互相切磋交流提高。另外,网络工程师、网管、服务器软硬件开发与...
  • MySQL的底层原理

    2020-12-21 15:39:35
    mysql的底层原理
  • 整个视频课程将由浅入深,介绍spring5源码的构建、spring5IOC容器的初始化过程、bean的声明周期过程、spring BeanFactoryPostporcessor并且结合原理给出当前流行的应用框架如何利用spring的源码知识写出优雅的代码,...
  • 第三方框架 AFNetworking 底层原理分析 AFNetworking主要是对NSURLSession和NSURLConnection(iOS9.0废弃)的封装,其中主要有以下类? 1. AFHTTPRequestOperationManager内部封装的是 NSURLConnection, 负责发送网络...
  • 集合底层原理

    千次阅读 2020-07-01 12:53:43
    Collection 单列集合 List 集合 ...一、ArrayList 原理 1.1 构造方法 ArrayList 底层是一个数组结构,当指定初始容量为0时返回的是 EMPTY_ELEMENTDATA,不指定容量时返回 DEFAULTCAPACITY_EMPTY...

    Collection 单列集合

    List 集合

    List 集合的三个子类:

       ArrayList:底层是数组,查询快(地址连续)、增删慢、线程非安全。

       LinkedList:底层是链表,查询慢、增删快、无索引、线程非安全。

       Vector:底层是数组,线程安全。

    一、ArrayList 原理

    1.1 构造方法

    ArrayList 底层是一个数组结构,当指定初始容量为0时返回的是 EMPTY_ELEMENTDATA,不指定容量时返回 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

    1.2 add 方法

    1. 确认list容量,尝试容量加1看有无必要,因为当添加一个元素后,可能对超过集合初始容量,将会引发扩容。如果没有超过初始容量则保存最小容量不变,无需对容量+1。

    2. 添加元素

    第一个方法得到数组的最小容量,避免资源浪费,第二个方法判断最小容量是否大于数组长度,大于则调用grow()进行扩容。

    grow()扩容的实现

    newCapacity 这里对数组容量扩容1.5倍,扩容完毕后调用 copyOf() ,完成对数组元素的拷贝。

    总的来说 add(E e) 的实现: 首先检查数组容量是否足够,够直接添加元素,不够进行扩容。

    1.3 get 方法

    检查角标是否越界,然后添加元素。

    1.4 set 方法

    检查是否越界,替换元素。

    1.5 remove() 方法

    numMoved 是需要移动的元素个数,从 index+1位置开始拷贝 numMoved 个元素 到数组的 index 位置,就等于将被删除元素后面的所有元素往前移动一个位置。因此List集合删除效率低。

    二、Vector 和 ArrayList 区别(面试)

    Vector 是同步的(线程安全),其内部方法都使用 synchronized 修饰,同样Vector因此效率比较低下。ArrayList 线程非安全。

    ArrayList 底层扩容是在原有基础上扩容1.5 倍,Vector是扩容 2 倍。

    三、LinkedList 原理

    LinkedList 集合特点:

    1. 底层是双向链表,查询慢,增删快。 2. 包含大量操作首尾的方法。

    3.1 add 方法

    了解过链表底层实现的应该对 LinkedList 的方法并不陌生,无论是添加还是删除方法,都拆分为 对头部和尾部元素的具体操作。

    这里 add 方法采用尾插法,同样也有 addFirst addLast 方法。

    3.2 remove 方法

    unlink(x) 完成对元素的删除,删除元素调用 equals 方法其实就是判断元素是否存在链表中,unlink 方法中实现了双向链表中删除元素的操作。

    将被删除节点断开,通过①②连接链表。

    3.3 get 方法

    判断下标是否合法,然后调用node方法获取链表元素。

    3.4 set 方法

    与 get 方法类似,根据下标判断从头遍历还是从尾遍历。

    Set 集合

    Set 集合的使用频率相比 List 集合较低,通常结合 set 集合 元素不可重复的特点进行一些操作,比如寻找只出现一次的数字、或者在实际项目中需要存储不可重复元素可以考虑使用 Set 集合。

    一、Set集合常用子类

    • HashSet集合

      • A:底层数据结构是HashMap

      • B:允许null,非同步

    • TreeSet集合

      • A:底层数据结构是红黑树(是一个自平衡的二叉树)

      • B:保证元素的排序方式,不允许null,非同步

    • LinkedHashSet集合

      • A:底层数据结构由HashMap和双向链表组成。

      • B:允许null

    二、HashSet集合

    java.util.HashSet 集合 implements Set接口

    HashSet是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于:hashCode与equals方法。

    2.1 HashSet特点:

        1.不允许存储重复元素,允许元素为null

        2.没有索引,没有带索引的方法,也没有for循环遍历

        3.是一个无序的集合,存储元素和取出元素的顺序有可能不一致

        4.底层是HashMap(查询速度非常快)

                Set<Integer> set = new HashSet<>(); //多态
                //使用add方法往集合中添加元素
                set.add(1);
                set.add(3);
                set.add(2);
                set.add(1);
                //使用迭代器遍历set集合
                Iterator<Integer> it = set.iterator();
                while(it.hasNext()){
                    Integer n = it.next();
                    System.out.println(n); //1,2,3 不允许存储重复元素,无序
                }
                //增强for遍历set集合
                for(Integer n:set){
                    System.out.print(n);
                }

    2.2 HashSet集合存储结构(哈希表)

    在JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理哈希冲突,同一hash值的链表都存储在一个链表里。但是当hash值相等的元素较多时,通过key值在链表中依次查找的效率较低。JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过(8)时,将链表转换为红黑树,这样大大减少了查找时间。

    要保证HashSet集合元素的唯一,就必须复写hashCode和equals方法建立属于当前对象的比较方式。(面试常考hashCode 和 equals 的联系)

    ① 重写 hashCode 必须同时重写equals。

    ② 相等(相同)的对象必须具有相等的哈希码(或者散列码)。

    ③ 如果两个对象的hashCode相同,它们并不一定相同。

    Map 双列集合

     java.util.Map<k,v>集合 存储的元素是键值对类型,key - value是一一对应的映射关系。

    Map集合特点:

    key 和 value 数据类型是任意的,一般我们习惯使用key为String类型,value为Object类型。

    key 不允许重复,value 可以重复,key只允许存在一个null的情况,value可以存在多个null值。

    一、Collection 与 Map的区别(面试)

    1. Map 集合存储元素是键值对的方式,键唯一,值可以重复。

    2. Collection 集合存储元素是单独出现的,Collection 的子接口Set值是唯一的,List是可重复的。

    二、哈希表

    List 集合底层是链表或者数组,存储的顺序和取出的顺序是一致的,但同样会带来一个缺点,想要获取某个元素,就要访问所有元素,直到找到为止。

    在哈希表中,我们不在意元素的顺序,能够快速查找到元素。哈希表中每个对象按照哈希值保存在对应的位置上。哈希表是由数组+链表实现的,每个列表称为桶,

    JDK1.8 之前 哈希值相同的对象以链表形式存储在一个桶中,这种情况称为哈希冲突,此时需要用该对象与桶上的对象进行比较,看看是否已经存在桶中,如果存在就不添加。(这个过程使用hashCode和equals进行判断,这也是之前我们说过为什么要同时重写hashCode和equals的原因),接下来了解了HashMap的put方法底层原理,应该会对为什么同时重写更加清晰了。

    JDK1.8 之后 当链表长度超过8,会从链表转换为红黑树结构当哈希表存储元素太多,需要对其进行扩展,创建一个桶更多的哈希表,那么什么时候需要进行扩容?装填因子(load factor)决定了何时进行扩展,装载因子默认为0.75,表中如果超过75%的位置已经填入元素,将进行双倍的扩展。

    三、HashMap 原理

    3.1 HashMap 类前注释解读

    主要讲了 HashMap 的一些特点:key value 允许为null不保证有序不同步(线程非安全),想实现同步调用Collections.synchronizedMap,装载因子为0.75。使用迭代器进行遍历。当知道要存储的元素个数时,尽可能设置初始容量。

    3.2 HashMap 属性

    当链表长度大于8,数组元素超过64 由链表结构转化为红黑树。

    JDK1.7 时,在实例化之后,底层创建了长度是16的Entry数组。

    JDK1.8 时,底层为Node数组,调用put方法后创建长度为16的数组。虽然长度为16,但是切记,负载因子0.75,因此数组只存放12个元素。

    3.3 put 方法

    put 方法是HashMap的核心,也是面试常考点。

    调用 hash(key) 方法,以key计算哈希值,hash 方法中得到key的hashCode 与 key的hashCode 高16位做异或运算,得到的值可以减少碰撞冲突的可能性。

    1、hash(key),取key的hashcode进行高位运算,返回hash值
    2、如果hash数组为空,直接resize()
    3、对hash进行取模运算计算,得到key-value在数组中的存储位置i
    (1)如果table[i] == null,直接插入Node<key,value>
    (2)如果table[i] != null,判断是否为红黑树p instanceof TreeNode。
    (3)如果是红黑树,则判断TreeNode是否已存在,如果存在则直接返回oldnode并更新;不存在则直接插入红黑树,++size,超出threshold容量就扩容
    (4)如果是链表,则判断Node是否已存在,如果存在则直接返回oldnode并更新;不存在则直接插入链表尾部,判断链表长度,如果大于8则转为红黑树存储,++size,超出threshold容量就扩容

    3.4 get 方法

    我们知道HashMap 是通过key找value,获取key的哈希值,调用getNode方法获取对应value。

    getNode 的实现比较简单,先判断计算出来的hashCode是否存在哈希表中,然后判断是否在桶的首位,不在则在链表或红黑树中进行遍历。

    3.5 remove 方法

    类似于put方法,这里就不贴源码,可以在util包下查看源码。

    计算key 的hash值,然后去找对应节点,找到后分三种情况进行删除:1. 链表 2. 红黑树 3. 桶的首位

    四、HashMap 与 Hashtable 对比

    1、继承的父类不同

    Hashable继承自Dictionary类,而HashMap继承自AbstractMap类。但二者都实现了Map接口。

    2、线程安全性不同

    HashTable是线程安全的,HashTable方法都加入了Synchronized,HashMap是非安全的。

    3、是否提供contains方法

    HashMap把contains方法去掉了,改成containsValue和containsKey,因为contains方法容易让人引起误解。

    Hashtable则保留了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同。

    4、key和value是否允许null值

    其中key和value都是对象,并且不能包含重复key,但可以包含重复的value。

    HashMap允许空值,键key最多只能1个null值,value允许多个null,HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。

    Hashtable中,key和value都不允许出现null值。

    5、两个集合遍历方式的内部实现上不同

    Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式

    6、hash值不同

    哈希值的使用不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

    7、内部实现使用的数组初始化和扩容方式不同

    HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

    图文并茂,对比很细,加粗部分可作为面试主答点。

    五、LinkedHashMap 原理

    5.1 LinkedHashMap 类前注释解读

    底层是哈希表+链表,允许为null,线程不同步,插入元素有序

    5.2 总结

    这里没有对LinkedHashMap具体方法进行解析,因为它继承自HashMap,在很多操作上使用的是HashMap的方法。而HashMap的方法我们上面已经进行了分析。

    六、TreeMap 原理

    6.1 TreeMap 类前注释解读

    底层是红黑树,实现NavigableMap 接口,可以根据key自然排序,也可以在构造方法上传递Camparator实现Map的排序。不同步

    TreeMap 实现NavigableMap 接口,而NavigableMap接口继承着SortedMap接口,致使我们的TreeMap是有序的。

    key不能为null。

    6.2 构造方法

        //comparator 维护的变量为null,使用自然排序
        public TreeMap() {
            comparator = null;
        }
        //设置一个维护变量传入
        public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
        }
        //调用putAll将Map转为TreeMap
        public TreeMap(Map<? extends K, ? extends V> m) {
            comparator = null;
            putAll(m);
        }
        //使用buildFromSorted转TreeMap
        public TreeMap(SortedMap<K, ? extends V> m) {
            comparator = m.comparator();
            try {
                buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
        }

    6.3 put 方法

    6.4 get 方法

    get 方法由getEntry进行具体实习

    getEntry

    当 comparator 不为null时,getEntryUsingComparator(Object key) 调用Comparator 自己实现的方法获取相应的值。

    6.5 总结

    TreeMap底层是红黑树,能够实现该Map集合有序

    如果在构造方法中传递了Comparator对象,那么就会以Comparator对象的方法进行比较。否则,则使用Comparable的compareTo(T o)方法来比较。(自然排序)

    • 值得说明的是:如果使用的是compareTo(T o)方法来比较,key一定是不能为null,并且得实现了Comparable接口的。

    • 即使是传入了Comparator对象,不用compareTo(T o)方法来比较,key也是不能为null的。

     七、ConcurrentHashMap

    重头戏来了~~~~

    7.1 JDK1.7和JDK1.8 不同

    1. JDK1.7 底层实现是:segments+HashEntry数组

    ConcurrentHashMap使用分段锁技术,Segment继承了ReentrantLock,每个片段都有了一个锁,叫做“锁分段

    我们知道Map中Hashtable是线程安全的,为什么要用ConCurrentHashMap?

    Hashtable 是在每个方法上都加上了Synchronized 完成同步,效率极其低下,而ConcurrentHashMap通过部分加锁利用CAS算法来实现同步。

    2. JDK 1.8底层实现是:哈希表+红黑树

    检索操作不用加锁,get方法是非阻塞的,key和value都不允许为空。

    取消了1.7的 segments 分段锁机制,采用CAS + volatile 乐观锁机制保证线程同步。

    7.2 CAS算法和volatile简单介绍

    1. CAS(Compare and swap,比较与交换)

    CAS 是一种基于乐观锁的操作。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住,等一个之前获得锁的线程释放锁之后,下一个线程才可以访问。而乐观锁采取了一种宽泛的态度,通过某种方式不加锁来处理资源,比如通过给记录加version来获取数据,性能较悲观锁有很大的提高。

    CAS有3个操作数

    • 内存值V

    • 旧的预期值A

    • 要修改的新值B

    当且仅当预期值A和内存值V相同时,将内存值V修改为B。CAS是通过无限循环来获取数据的,若果在第一轮循环中,a线程获取地址里面的值被b线程修改了,那么a线程需要自旋,到下次循环才有可能机会执行。

    2. volatile 关键字

    volatile仅仅用来保证该变量对所有线程的可见性,但不保证原子性

    可见性:在多线程环境下,当被volatile修饰的变量修改时,所有的线程都可以知道该变量被修改了

    不保证原子性:修改变量(赋值)实质上是分为好几步操作,在这几步操作中是不安全的。

    7.2 put 方法

    put操作采用CAS+synchronized 实现并发插入或更新操作。

    • 如果没有初始化就先调用initTable()方法来进行初始化过程
    • 如果没有hash冲突就直接CAS插入
    • 如果还在进行扩容操作就先进行扩容
    • 如果存在hash冲突,就加 synchronized 锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入,
    • 最后一个如果Hash冲突时会形成Node链表,在链表长度超过8,Node数组超过64时会将链表结构转换为红黑树的结构,break再一次进入循环
    • 如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容

     initTable 方法的实现

    当要初始化时会通过CAS操作将sizeCtl置为-1,而sizeCtl由volatile修饰,保证修改对后面线程可见。
    这之后如果再有线程执行到此方法时检测到sizeCtl为负数,说明已经有线程在给扩容了,这个线程就会调用Thread.yield()让出一次CPU执行时间。

    7.3 get 方法

    我们之前说到 get 操作不用加锁,是非阻塞的,因为 Node 节点被重写了,设置了volatile关键字修饰,致使它每次获取的都是最新设置的值。

    八、CopyOnWriteArrayList 原理

    CopyOnWriteArrayList是线程安全容器(相对于ArrayList),底层通过复制数组的方式来实现。

    CopyOnWriteArrayList在遍历的使用不会抛出ConcurrentModificationException异常,并且遍历的时候就不用额外加锁。

    8.1 CopyOnWriteArrayList 基本结构

    CopyOnWriteArrayList底层是数组,加锁交由ReentrantLock来完成

        //可重入锁对象
        final transient ReentrantLock lock = new ReentrantLock();
    
        //CopyOnWriteArrayList底层由数组实现,volatile修饰
        private transient volatile Object[] array;
    
        //得到数组
        final Object[] getArray() {
            return array;
        }
        //设置数组
        final void setArray(Object[] a) {
            array = a;
        }
    
        //初始化数组
        public CopyOnWriteArrayList() {
            setArray(new Object[0]);
        }

    8.2 add 方法

        public boolean add(E e) {
            //加锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                //得到原数组长度和元素
                Object[] elements = getArray();
                int len = elements.length;
                //复制一个新数组
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                //将元素添加到新数组
                newElements[len] = e;
                //将volatile Object[] array 的指向替换成新数组
                setArray(newElements);
                return true;
            } finally {
                lock.unlock();
            }
        }

    在添加的时候上锁,并复制一个新数组,添加操作在新数组上完成,将array指向到新数组中,最后解锁。

    8.3 set 方法

        public E set(int index, E element) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                //得到原数组旧值
                Object[] elements = getArray();
                E oldValue = get(elements, index);
                //判断新值和旧值是否相等
                if (oldValue != element) {
                    int len = elements.length;
                    //复制新数组,在新数组中完成修改
                    Object[] newElements = Arrays.copyOf(elements, len);
                    newElements[index] = element;
                    //array引用指向新数组
                    setArray(newElements);
                } else {
                    // Not quite a no-op; ensures volatile write semantics
                    setArray(elements);
                }
                return oldValue;
            } finally {
                lock.unlock();
            }
        }
    • 在修改时,复制出一个新数组,修改的操作在新数组中完成,最后将新数组交由array变量指向

    • 写加锁,读不加锁,读取数据是在原数组,因此保证了多线程下的数据一致性。

    • 类似于读写分离的思想,读和写分别在不同的容器完成,写时进行读操作并不会读到脏数据。

    8.4 CopyOnWriteArrayList缺点

    占用内存:如果CopyOnWriteArrayList经常要增删改里面的数据,经常要执行add()、set()、remove()进行新数组创建,那是比较耗费内存的。

    数据一致性:CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性

    面试题总结

    上面标注(面试)的这里就不再阐述。。。

    List 和 Map的区别

    存储结构不同:List 是存储单列的集合,Map是存储key-value键值对的集合

    元素是否可重复:List 允许重复元素,Map不允许key重复

    是否有序:List集合是有序的(存储有序),Map集合是无序的。

    Collection和Collections的区别

    Collection是集合的上级接口,继承它的有Set和List接口

    Collections是集合的工具类,提供了一系列的静态方法对集合的搜索、查找、同步等操作

    ArrayList,Vector,LinkedList的存储性能和特征?

    ArrayList和Vector都是使用数组方式存储元素,可以直接按照索引查找元素、访问快、增删慢(相对的,极端情况不考虑)。

    LinkedList使用双向链表存储数据、查找慢、增删快(相对的,极端情况不考虑)。

    Vector使用了synchronized方法,线程安全,性能上较ArrayList差。LinkedList也是线程不安全的,LinkedList提供了一些方法,使得它可以被当作堆栈或者队列来使用。

    Java中HashMap的key值要是为类对象则该类需要满足什么条件?

    需要同时重写该类的hashCode()方法和equals方法。

    原因:

    插入元素时先计算hashCode值,相等则调用 equals() 方法,两个key相同替换元素值,两个key不相同,说明 hashCode 值是碰巧相同,则将新增元素放在桶里。

    我们一般认为,只要两个对象的成员变量的值是相等的,那么我们就认为这两个对象是相等的,因此要重写equals()f方法,重写了equals(),就必须重写hashCode()方法,因为equals()认定了这两个对象相同,而同一个对象调用hashCode()方法时,是应该返回相同的值的!

    展开全文
  • STM32程序底层原理.pdf

    2020-07-06 11:22:04
    STM32程序底层原理.pdf
  • Git 底层原理

    千次阅读 2019-05-17 10:32:01
    文章目录@[toc]一.git 介绍一.git 简介二.git 历史三.集中式与分布式四.git 大致结构二..git 目录...开始从底层入手 git七.git add 命令底层原理八.git add 和 git commit 中间的操作(tree 对象的生成)九.git comm...


    这里有几篇 git 相关的博文推荐

    git 常用命令

    git 常见场景操作

    一.git 介绍

    git 底层原理的讲解中看到一篇非常非常赞的博文,此文中有很多内容摘自下面这篇博文,做了小汇总,强烈推荐

    Yelbosh 大神的 git 博文

    一.git 简介

    目前最先进的开源分布式版本控制系统,来源思想是,代码开发了多个版本,以往的思想是每个版本在电脑中 copy 一份保存,以免以后版本的代码出现问题,可以直接找之前几个版本的代码,这种就好似只有两层多子树的树形结构,git 的思想是自己电脑中不用 copy 下来每个版本,每个版本逻辑上是一个结点,每次更新到下一个版本,结点就自动往后延伸,是一个线性结构,若想恢复到之前哪个版本,也就是恢复到之前哪个结点,可以用 git 相关命令来将版本变为历史版本。git 比其他版本控制优秀在于其跟踪管理是改动而不是文件本身

    二.git 历史

    1991 年 Linus 创建了开源的 Linux,自此 Linux 不断发展成为服务器系统首选,2002 年之前各地开源 Linux 的代码贡献者通过 diff 方式把源代码发给 Linus,然后 Linus 本人通过手工方式合并代码,Linus 那时坚定反对 CSV 和 SVN,因为这些集中式版本控制系统不但速度慢而且需要联网才行,虽然有一些好用的商用版本控制系统,可惜需要付费,这与 Linus 提倡的开源精神不符合,到 2002 年 Linux 代码库已经大到 Linus 很难维护了,社区成员也对此表示不满,于是 Linus 选择使用了商业版本控制系统 BitKeeper,该系统的公司处于人道主义授权 Linux 社区免费使用该版本控制系统,可是在 2005 年的时候,Liunx 社区中的开发 Samba 的安德鲁视图破解 BitKeeper 协议,其实还有社区里的其他人,被 BitKeeper 公司发现,一气之下,公司决定收回 Linux 社区免费授权,之后 Linus 没有选择向 BitKeeper 所有的公司道歉,而是选择自己花了两周左右的时间自己用 C 写了一个分布式版本控制系统,这就是 Git,一个月的之内 Linux 系统源码已经可以被 Git 管理了,接着 Git 就迅速成为最流行的分布式版本控制系统,2008 年的时候,GitHub 上线,无数开源项目通过 Git 存储在 GitHub 中直到现今

    三.集中式与分布式

    • 集中式

      版本库放置于中央服务器,常规操作是先从中央库拉取最新版本信息,之后在自己电脑中修改,再把新版本推送给中央服务器。但需要联网才能操作,速度慢。常见有 SVN,CSV 等

    • 分布式

      每个人电脑里都有个版本库,有个人电脑坏掉,不要紧可以直接从其他人电脑复制一份过来即可,但实际使用中,很少有人在两人之间电脑推送修改,为了方便交换,通常也有个类似中央服务器的电脑,但是其仅仅是为了方便大家代码统一在此处交换

    四.git 大致结构

    git 工作区有个隐藏目录 .git,这是 git 的版本库,其中有暂存区,默认的 master 分支以及指向 master 的 HEAD 指针

    二. .git 目录结构

    img

    进入隐藏的 .git 目录之后可以看到如上图所示结构

    • 核心文件:config,objects,HEAD,index,refs 这 5 个文件夹

      • config:这里存储项目的一些配置信息,比如是否以 bare 方式初始化,remote 信息等。git remote add 添加的远程分支信息就保存在这里
      • objects:这里保存 git 对象,git 中的一些操作以及文件都会以 git 对象形式保存在这里,git 对象分为 BLOBtreecommit 三种类型,比如 git commit 就是 commit 类型变量,各个版本之间通过版本树进行组织,比如 HEAD 指向某个 commit 对象,而 commit 对象又会指向几个 BLOB 对象或者 tree 对象。objects 文件夹中有很多子文件夹,其中 git 对象保存在以其 sha-1 值的前两位为子文件夹后 38 位为文件名的文件中,此外 git 为了节省存储对象所占用的磁盘空间,会定期对 git 对象进行压缩和打包,其中 pack 文件夹用于存放打包压缩的对象,info 文件夹用于从打包的文件中查找 git 对象
      • HEAD:该文件指明了本地的分支结果,如本地分支是 master,那么 HEAD 就指向 master,分支在 refs 中就会表示成refs:refs/heads/master
      • index:该文件 stage 暂存区信息,也就是 add 之后保存到的区域,内容包括它指向的文件的时间戳,文件名,sha1 值等
      • refs:该文件夹保存了指向分支的提交对象也就是 commit 对象的指针,其中的 heads 文件夹存储了本地每一个分支最近一次提交的 sha-1 值,即 commit 对象的 sha-1 值,每个分支一个文件;remotes 文件夹则记录你最后一次和远程仓库的通信,也就是说这里会记录最后一次每个分支推送到远端的值;tags 文件夹存储分支别名
    • sha-1 算法介绍说明:其实 sha-1 算法在两千零几年中国已经被攻破,有人就提出 git 的安全性问题,由于 git 是 linus 在此算法还没被攻破时候创建,linus 现在不以为然,因为他认为没有人会发这么大经理偷偷篡改他人代码树,他认为即使是使用老掉牙的 md5 都是可行,未来 git 中的 sha-1 算法还是有可能被替换,参见 http://www.itxm.cn/post/14240.html

    • 其他文件

      • hooks:这里主要定义了客户端或服务端的 hook 脚本,这些脚本用于在特定命令和操作之前、之后进行特殊处理
      • description:仅供 GitWeb 程序使用
      • logs:记录了本地仓库和远程仓库的每一个分支的提交信息,即所有 commit 对象都会被记录在此,这个文件夹内容应该是我们查看最频繁的,如 git log
      • info:其中保存了一份不希望在 .gitignore 文件中管理的忽略的全局可执行文件
      • COMMIT_EDITMSG:记录了最后一次提交时的注释信息

      我们可以看到 .git 目录中的文件会因为几次提交就成倍的增长,因为其中要生成对象

    三.git add 与 git commit 简单原理

    平时我们在工作区修改文件,没有 add 操作之前我们通过 git status 命令可以查看到有文件被 modified 而且是 not staged,这个时候修改的文件仅仅是在工作区内,之后通过 git add 操作,被修改的文件从工作区提交到暂存区(驿站)也就是 stage 里,再通过 commit 操作把暂存区 stage 中所有的内容全部提交到当前的分支结构当中,即

    工作区(文件修改后 add 前)→ stage 暂存区(add 后 commit 前)→ 本地分支结构(本地 commit 后)

    这样的一种三层结构

    四.创建与合并分支简单原理

    分支被合并可以被 -d 删除,分支没有被合并后 -d 删除会出错,需要 -D 强制删除

    • master分支
      一个分支就是一条时间线,默认有一条时间线master,其中有个指针master,这个master指针是指向提交的,还有个HEAD指针,这个指针是指向当前的指向提交的指针的指针,也就是指向当前分支的指针。每次提交,master指针都会向后移一位,这样不断去提交,master分支就会越来越长。如下图1:
      图1
    • 创建dev新分支
      若创建新分支,如dev分支,git会新建一个dev指针,与master指针功能一样。先是指向和master同样的位置,当checkout切换到dev分支时候,HEAD指针就指向了dev指针了,当在dev分支下提交,master指针不动。如下图2和图3:
      图2
      图3
    • 分支的合并
      分支合并,操作很简单,若将dev分支内容合到master上,就是将master的指针指向dev指针指向的位置即可,如图4:
      图4
    • 删除dev分支
      删除分支就是讲dev指针删除掉,如图5:
      图5

    五.git rebase 简单原理

    把一个分支的修改整合到另一个分支的办法有两种,第一种就是 git merge 操作,另一种就是 git rebase 操作,该命令原理就是回到两个分支最近的共同祖先,根据当前分支(也就是要进行衍合的分支experiment)后续的历次提交对象(这里只有一个 C3),生成一系列文件补丁,然后以基底分支(也就是主干分支master)最后一个提交对象(C4)为新的出发点,逐个应用之前准备好的补丁文件,最后会生成一个新的合并提交对象(C3’),从而改写 experiment 的提交历史,使它成为 master 分支的直接下游。如下图所示:

    img

    在rebase的过程中,也许会出现冲突。在这种情况,Git会停止rebase并会让你去解决冲突;在解决完冲突后,用git add命令去更新这些内容的索引, 然后,你无需执行git-commit,只要执行git rebase –continue,这样git会继续应用(apply)余下的补丁。如果要舍弃本次衍合,只需要git rebase --abort即可。切记,一旦分支中的提交对象发布到公共仓库,就千万不要对该分支进行rebase操作

    六.开始从底层入手 git

    git 命令分为 procelain 和 plumbing 命令,前者是基于后者来实现的,若把 git 看成一个操作系统那么 plumbing 命令更像是一个 shell 命令,而 procelain 命令就像是通过利用 shell 命令编写的一系列系统功能或工具,下面会重点讲解 plumbing 命令以及 git 对象

    • plumbing 命令

      git 本质上一套内容寻址(content-addressable)文件系统,寻址无非就是查找,这样的寻址系统对于完成过 linux 系统构建的 linus 肯定不算难事。寻址无非就是查找,git 采用的是 HashTable 的方式进行查找,即 git 是通过简单键值对形式实现内容寻址,键就是文件(头+内容)的哈希值(前面 .git 目录结构中也讲了采用 sha-1 加密方式,40位,点击这里跳转到前面),值是经过压缩后的文件内容,plumbing 操作实际上是 40 位的哈希值来进行压缩包的查找

      git 对象存储方式表示式:

      Key = sha1(file_header + file_content) 
      Value = zlib(file_content)
      
    • git 对象

      前面也讲了 git 对象有 BLOB(binary large object),tree,commit 三种,点击这里跳转到前面,BLOB 存储几乎所有的文件类型,BLOB 大的二进制表示的对象,和数据库中 BLOB 类型,常用来存储数据库中图片视频是一样的;tree 是用来组织 BLOB 对象的一种数据类型,你完全可以理解成二叉树中的树结点,只不过 git 中的可是“多叉树”,commit 对象表示每一次的提交操作,是由 tree 对象衍生出来,通过每次提交,这样所有的 commit 操作便可连成一个提交树,一个 branch 实际上就是这个大树中的一个子树

    七.git add 命令底层原理

    stage 暂存区又叫索引库,因为暂存区信息内容保存在 .git 目录结构的 index 文件夹,git add 就是把工作区 modified 文件添加到 stage 暂存区,那么 git add 底层是如何通过 plumbing 命令完成文件索引操作的?

    • git add 对应着的两个基本 plumbing 命令

      git hash-object #获取指定文件的key,如果带上-w选项,则会将该对象的value进行存储
      git update-index #将指定的object加入索引库,需要带上—add选项
      

      先用第一个命令将需要暂存的文件进行 key-value 转化成 git 对象,进行存储(.git 中的 objects 文件夹中),拿到这些文件的 key,然后通过第二条命令将这些对象加入到 stage 暂存区中暂存(.git 中的 index 文件夹中)

      若还要根据 git 对象的 key 来查看文件信息,需要如下 plumbing 命令

      git cat-file –p/-t key #获取指定key的对象信息,-p打印详细信息,-t打印对象的类型
      

      也就是说 git add 命令本质上就是把工作区修改的文件变成 git 对象并且拿到 sha-1 值放在 objects 文件夹中,然后连同 key 一起转存到另一个 index 文件夹中(暂存区)。实际上 index 库记录是从项目初始化起,每次 add 在这里都会把文件的索引信息(时间戳和大小)更新,也就是说这个库只会越来越大

    八.git add 和 git commit 中间的操作(tree 对象的生成)

    在这里插入图片描述
    git 中所有内容以 BLOB 或者 tree 对象形式存储。如果把 git 看做 unix 系统,那么 tree 对象就好似文件系统中的目录,BLOB 对象就好似 inodes 或文件内容。我们平时操作的 add 和 commit 操作似乎没有涉及到这个 tree 对象的生成,其实有的,tree 对象只是 add 和 commit 中间的一个缓冲步骤,因为 commit 对象要根据 tree 对象来创建,下面创建 tree 对象:

    git write-tree #根据索引库中的信息创建tree对象
    

    这条命令的作用是返回生成 tree 对象的 key 值

    整个工作目录对应一个 tree 对象,并且其下每一个子文件夹都是一个 tree 对象,每次的 commit 对象都对应着根 tree 对象,任何一个对象的改变都会导致其上层所有 tree 对象的重新存储

    img

    九.git commit 命令底层原理

    index 暂存区包括了项目仓库中所有的文件,commit 对象所对应的 tree 对象永远都是工作区根目录所对应的 tree 对象,也就是说每次 commit 之后,commit 对象会依附在这个工作区的 tree 对象上。要是仔细观察目录结构的话,可以发现对象文件夹,子文件夹对应着一个 tree 结点,文件的话对应着一个 BLOB 结点,创建 commit 对象的命令:

    git commit-tree key –p key2 #根据tree对象创建commit对象,-p表示前继commit对象
    

    该命令实现的操作类似于数据结构树中增加结点的操作,在这个命令中若是第一次提交则不需要指定 -p 选项指明父节点


    下一篇

    git 常用命令

    git 常见场景操作

    展开全文
  • 此文承接java集合的底层原理(List的底层原理),具体可以此文的开头讲述,此处简要概述的map的结构如下 Map 接口 键值对的集合 (双列集合) ├———Hashtable 接口实现类, 同步, 线程安全 ├———HashMap ...

     此文承接  java集合的底层原理(List的底层原理),具体可以此文的开头讲述,此处简要概述的map的结构如下

    Map 接口 键值对的集合 (双列集合)
    ├———Hashtable 接口实现类, 同步, 线程安全
    ├———HashMap 接口实现类 ,没有同步, 线程不安全-
    │—————–├ LinkedHashMap 双向链表和哈希表实现
    │—————–└ WeakHashMap
    ├ ——–TreeMap 红黑树对所有的key进行排序
    └———IdentifyHashMap
     

    一、HashMap

    1.1  概述  

           HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null 建和null值, 因为key不允许重复,因此只能有一个键为null,另外HashMap不能保证放入元素的顺序,它是无序的,和放入的顺序并不能相同。HashMap是线程不安全的

           在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。


    从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表。当新建一个HashMap的时候,就会初始化一个数组。

     java源码如下:

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;
    
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
        ……
    }

    1.2 HashMap实现存储读取元素

       先看存储源码:

    public V put(K key, V value) {
        //调用putVal()方法完成
        return putVal(hash(key), key, value, false, true);
    }
     
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断table是否初始化,否则初始化操作
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //计算存储的索引位置,如果没有元素,直接赋值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //节点若已经存在,执行赋值操作
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断链表是否是红黑树
            else if (p instanceof TreeNode)
                //红黑树对象操作
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //为链表,
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度8,将链表转化为红黑树存储
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //key存在,直接覆盖
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //记录修改次数
        ++modCount;
        //判断是否需要扩容
        if (++size > threshold)
            resize();
        //空操作
        afterNodeInsertion(evict);
        return null;
    }
    

    根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

    hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突。

    我们可以看到在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表,这样就大大优化了查询的效率。

    根据上面 put 方法的源代码可以看出,当程序试图将一个key-value对放入HashMap中时,程序首先根据该 key的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry的 value,但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

    读取元素源码 

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
            e != null;
            e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

    从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

    总结起来就是:

           HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

    1.3 HashMap的扩容

           当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。

    所以扩容必须满足两条件

    • 存放新值的时候当前已有元素必须大于阈值;
    • 存放新值的时候当前存放数据发生hash碰撞(当前key计算的hash值计算出的数组索引位置已经存在值)

           那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题。

    总结:

    1、HashMap是基于哈希表的Map接口的非同步实现,允许使用null值和null键,但不保证映射的顺序。
    2、底层使用数组实现,数组中每一项是个单向链表,即数组和链表的结合体;当链表长度大于一定阈值(8)时,链表转换为红黑树(在Jdk1.8的优化),这样减少链表查询时间。
    3、HashMap在底层将key-value当成一个整体进行处理,这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对,当需要存储一个Node对象时,会根据key的hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Node时,也会根据key的hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Node。
    4、HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置,很耗性能
    5、采用了Fail-Fast机制,通过一个modCount值记录修改次数,对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map,马上抛出异常
          

    二、HashTable

    2.1 概述

    和HashMap一样,HashTable也是一个散列表,它存储的内容是键值对映射。HashTable继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。HashTable的函数都是同步的,这意味着它是线程安全的。它的Key、Value都不可以为null。此外,HashTable中的映射不是有序的。

    HashTable的实例有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量就是哈希表创建时的容量。注意,哈希表的状态为open:在发生“哈希冲突”的情况下,单个桶会存储多个条目,这些条目必须按顺序搜索。加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用rehash方法的具体细节则依赖于该实现。通常,默认加载因子是0.75。
     

    2.2  数据结构

    HashTable与Map关系如下

     

    public class Hashtable<K,V>  
        extends Dictionary<K,V>  
        implements Map<K,V>, Cloneable, java.io.Serializable 
    

    HashTable并没有去继承AbstractMap,而是选择继承了Dictionary类,Dictionary是个被废弃的抽象类

     

    2.3  实现原理

    成员变量跟HashMap基本类似,但是HashMap更加规范,HashMap内部还定义了一些常量,比如默认的负载因子,默认的容量,最大容量等。

    public Hashtable(int initialCapacity, float loadFactor) {//可指定初始容量和加载因子  
            if (initialCapacity < 0)  
                throw new IllegalArgumentException("Illegal Capacity: "+  
                                                   initialCapacity);  
            if (loadFactor <= 0 || Float.isNaN(loadFactor))  
                throw new IllegalArgumentException("Illegal Load: "+loadFactor);  
            if (initialCapacity==0)  
                initialCapacity = 1;//初始容量最小值为1  
            this.loadFactor = loadFactor;  
            table = new Entry[initialCapacity];//创建桶数组  
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//初始化容量阈值  
            useAltHashing = sun.misc.VM.isBooted() &&  
                    (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
        }  
        /** 
         * Constructs a new, empty hashtable with the specified initial capacity 
         * and default load factor (0.75). 
         */  
        public Hashtable(int initialCapacity) {  
            this(initialCapacity, 0.75f);//默认负载因子为0.75  
        }  
        public Hashtable() {  
            this(11, 0.75f);//默认容量为11,负载因子为0.75  
        }  
        /** 
         * Constructs a new hashtable with the same mappings as the given 
         * Map.  The hashtable is created with an initial capacity sufficient to 
         * hold the mappings in the given Map and a default load factor (0.75). 
         */  
        public Hashtable(Map<? extends K, ? extends V> t) {  
            this(Math.max(2*t.size(), 11), 0.75f);  
            putAll(t);  
        }  
    

    为避免扩容带来的性能问题,建议指定合理容量。跟HashMap一样,HashTable内部也有一个静态类叫Entry,其实是个键值对,保存了键和值的引用。也可以理解为一个单链表的节点,因为其持有下一个Entry对象的引用

     

    2.3 存取实现

      存数据

    public synchronized V put(K key, V value) {//向哈希表中添加键值对  
            // Make sure the value is not null  
            if (value == null) {//确保值不能为空  
                throw new NullPointerException();  
            }  
            // Makes sure the key is not already in the hashtable.  
            Entry tab[] = table;  
            int hash = hash(key);//根据键生成hash值---->若key为null,此方法会抛异常  
            int index = (hash & 0x7FFFFFFF) % tab.length;//通过hash值找到其存储位置  
            for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {/遍历链表  
                if ((e.hash == hash) && e.key.equals(key)) {//若键相同,则新值覆盖旧值  
                    V old = e.value;  
                    e.value = value;  
                    return old;  
                }  
            }  
            modCount++;  
            if (count >= threshold) {//当前容量超过阈值。需要扩容  
                // Rehash the table if the threshold is exceeded  
                rehash();//重新构建桶数组,并对数组中所有键值对重哈希,耗时!  
                tab = table;  
                hash = hash(key);  
                index = (hash & 0x7FFFFFFF) % tab.length;//这里是取摸运算  
            }  
            // Creates the new entry.  
            Entry<K,V> e = tab[index];  
            //将新结点插到链表首部  
            tab[index] = new Entry<>(hash, key, value, e);//生成一个新结点  
            count++;  
            return null;  
        }  
    

    取数据

    public synchronized V get(Object key) {//根据键取出对应索引  
          Entry tab[] = table;  
          int hash = hash(key);//先根据key计算hash值  
          int index = (hash & 0x7FFFFFFF) % tab.length;//再根据hash值找到索引  
          for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {//遍历entry链  
              if ((e.hash == hash) && e.key.equals(key)) {//若找到该键  
                  return e.value;//返回对应的值  
              }  
          }  
          return null;//否则返回null  
      }  
    

     

    总结:

    1、Hashtable是基于哈希表的Map接口的同步实现,不允许使用null值和null键底层使用数组实现,数组中每一项是个单链表,即数组和链表的结合体
    2、Hashtable在底层将key-value当成一个整体进行处理,这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对,当需要存储一个Entry对象时,会根据key的hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据key的hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。
    3、HashTable中若干方法都添加了synchronized关键字,也就意味着这个HashTable是个线程安全的类,这是它与HashMap最大的不同点

    4、HashTable每次扩容都是旧容量的2倍加2,而HashMap为旧容量的2倍。

       

    展开全文
  • Android开发环境Android基础知识
  • Javascript底层原理总结

    千次阅读 2020-10-22 13:12:29
    Javascript底层原理、面试题、算法、浏览器、dom等相关

     

    文档持续更新~

    目录

    基础

    数据结构

    JS堆栈的概念

    作用域链的理解

    变量提升、函数提升、浏览器解析变量的机制

    理解上下文和作用域

    定义一个变量到这个变量被回收做了什么

    进程与线程、什么是单线程?和异步有何关系

    理解MVVM、MVC

    理解AMD、commonjs

    虚拟内存及缓冲区溢出

    null和undefined的区别

    ajax/axios/fetch的区别

    Promise的原理

    instanceof的原理

    typeof的原理

    数组的扁平化

    xhr对象

    ES6 Proxy的概念

    闭包?运行时上下文里面包括什么?

    结合作用域链看闭包

    三栏布局

    BFC布局原理

    事件

    even loop事件循环

    DOM事件

    js事件流

    js防抖和节流

    事件委托原理以及优缺点

    回流/重绘

    浏览器相关

    在地址栏输入url到最终展示界面期间发生了什么

    http、https的区别

    同源策略、跨域及原理

    缓存及更新问题

    新一代的前端存储方案--indexedDB

    webview与原生应用交互

    DOM

    获取DOM节点的几个方法

    如何给DOM节点上添加事件

    服务器端知识


    基础

    • 数据结构

    :一种遵从先进后出 (LIFO) 原则的有序集合;新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端为栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。只是对原有数据进行了一次封装而已。而封装的结果是:并不去关心其内部的元素是什么,只是去操作栈顶元素,这样的话,在编码中会更可控一些

    // 定义一个栈
    class Stack {
        constructor() {
            this.items = []
        }
        push(element) { // 入栈
             this.items.push(element)
        }
        pop() {    // 出栈 
            return this.items.pop()
        }
        get peek() {    // 末位
            return this.items[this.items.length - 1]
        }
        get isEmpty() {    // 是否为空栈
            return !this.items.length
        }
        get size() {    // 尺寸
            return this.items.length
        }
        clear() {    // 清空栈
            this.items = []
        }
        print() {    // 打印栈数据
            console.log(this.items.toString())
        }
    }
    const stack = new Stack()
    console.log(stack.isEmpty) // true
    
    // 添加元素
    stack.push(5)
    stack.push(8)
    
    // 读取属性再添加
    console.log(stack.peek) // 8
    stack.push(11)
    console.log(stack.size) // 3
    console.log(stack.isEmpty) // false

     

    队列:与上相反,一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项;队列在尾部添加新元素,并从头部移除元素。最新添加的元素必须排在队列的末尾。例如日常生活中的购物排队。与栈类比,栈仅能操作其头部,队列则首尾均能操作,但仅能在头部出尾部进

    class Queue {
        constructor(items) {
            this.items = items || []
        }
        enqueue(element){ // 向队列尾部添加一个(或多个)新的项
            this.items.push(element)
        }
        dequeue(){ // 移除队列的第一(即排在队列最前面的)项,并返回被移除的元素
            return this.items.shift()
        }
        head(){ // 返回队列第一个元素,队列不做任何变动
            return this.items[0]
        }
        clear(){ // 清空队列
            this.items = []
        }
        get size(){ // 返回队列内元素个数
            return this.items.length
        }
        get isEmpty(){ // 队列内无元素返回 true,否则返回 false
            return !this.items.length
        }
        print() {
            console.log(this.items.toString())
        }
    }

    链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的;每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(指针/链接)组成。

    集合:由一组无序且唯一(即不能重复)的项组成;这个数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中。

    字典:以 [键,值] 对为数据形态的数据结构,其中键名用来查询特定元素,类似于 Javascript 中的Object

    散列:根据关键码值(Key value)直接进行访问的数据结构;它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度;这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    :由 n(n>=1)个有限节点组成一个具有层次关系的集合;把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的,基本呈一对多关系,树也可以看做是图的特殊形式。

    :图是网络结构的抽象模型;图是一组由边连接的节点(顶点);任何二元关系都可以用图来表示,常见的比如:道路图、关系图,呈多对多关系。

    数据结构详细地址点这里

     

    • JS堆栈的概念

    (heap)用于复杂数据类型(引用类型)分配空间,例如数组对象、object对象;它是运行时动态分配内存的,因此存取速度较慢。

    (stack)中主要存放一些基本类型的变量和对象的引用,(包含池,池存放常量),其优势是存取速度比堆要快,并且栈内的数据可以共享,但缺点是存在栈中的数据大小与生存期必须是确定的,缺乏灵活性,先进后出,后进先出原则,所以 push 优于 unshift。

    js的数据类型主要分为两种:基本类型值引用类型值

    基本类型值 有6种:undefined,null,boolean,number,string,symbol。这六种数据类型是按值访问的,是存放在栈内存中的简单数据段,数据大小确定,内存空间大小可以分配。基本类型值的复制是值的传递,赋值以后二者再无关联,修改其中一个不会影响另一个。

    引用类型值: 5种基本类型值以外的数据类型都可以看做是引用类型值,比如array,object等,是保存在堆内存中的对象。js不允许直接访问堆内存中的位置,也就是说不能直接操作对象的内存空间。在操作对象时,实际是在操作对象的引用而不是实际的对象,是按地址访问的。

    可以看到,直接传递引用类性值的时候,传递的只是引用,二者指向同一块内存,所以修改其中一个,必然会引起另一个变量的变化。 在日常的使用中,我们把对象赋值给一个变量时,通常希望得到的是一个跟原对象无关的副本,修改新的变量不影响原对象,因此就有了浅拷贝深拷贝。 

     

    • 作用域链的理解

    作用域链是由于js的变量都是对象的属性,而该对象可能又是其它对象的属性,而所有的对象都是window对象的属性,所以这些对象的关系可以看作是一条链

    javascript查找与变量相关联的值时,会遵循一定的规则,也就是沿着作用域链从当前函数作用域内逐级的向上查找,直到顶层全局作用域结束,若找到则返回该值,若无则返回undefined,这个链条是基于作用域的层次结构的,一旦当代码在坏境中执行时,会自动的创建一个变量对象的作用域链,其作用域链的用途也就是保证对执行坏境的全局变量和具有访问权限函数内的局部变量定制特殊的规则,由内到外有序的对变量或者函数进行访问,作用域链包含了在坏境栈中的每个执行坏境对应的变量对象,通过作用域链可以决定变量的访问与标识符的解析

    作用域就是变量与函数的可访问范围,即作用域控制着变量与函数的可见性和生命周期。在JavaScript中,变量的作用域有全局作用域和局部作用域两种。

    全局作用域:可以在代码的任何地方访问,一般来说,下面情况的对象会在全局作用域中:

                  最外层函数和在最外层函数外面定义的变量。

                  没有通过关键字"var"声明的变量。

                  浏览器中,window对象的属性。

    局部作用域:函数作用域(Function scope),所有的变量和函数只能在作用域内部使用

     

    • 变量提升、函数提升、浏览器解析变量的机制

    JS预解析:

        1.当浏览器加载html页面的时候,首先会提供一个全局JS代码执行的环境(全局作用域)

        2.预解析(变量提升,浏览器的加载机制)

        在当前的作用域中,js代码执行之前,浏览器首先会默认把所有带var和function的进行提前的声明或者定义

        注意:对于变量只是进行了变量提前声明,而函数是提前声明并且定义

    var num = 1;
    // 理解声明和定义
    //    声明(declare):var num; --> 告诉浏览器在全局作用域中有一个num的变量了,如果一个变量只是声明了但是没有赋值,默认的值是undefined。
    //    定义(defined):num = 1; --> 给变量进行赋值
    //    var ->在预解释的时候只是提前的声明
    //    function ->在预解释的时候提前的声明+定义都完成了
    console.log(number);  // num is not defined
    console.log(num); // undefined
    var num = 1;
    console.log(num); // 1
    
    console.log(fn); // 打印出函数体
    function fn (){
        console.log('fn')
    };
    console.log(fn); // 打印出函数体

     变量和函数重名时:变量只是提前声明了,函数声明并且定义了,所以先打印的fn,然后开始执行时,变量开始赋值,函数不进行赋值。

    console.log(fn) // fn(){console.log(4)}
    function fn(){
        console.log(2)
    }
    console.log(fn) //  // fn(){console.log(4)}
    var fn = 3
    console.log(fn) // 3
    function fn(){
        console.log(4)
    }
    console.log(fn) // 3

        函数表达式调用必须写到函数表达式的下面

    fun(); // fun is not a function
    var fun = function () {
        console.log(22);
    }
    相当于执行
    var fun;
    fun();
    fun = function () {
        console.log(22);
    }
    

        3.预解析只发生在当前的作用域(全局作用域/局部作用域)下,例如:开始只对window下的进行预解释,只有函数执行的时候才会对函数中的进行预解析

    var a = 10;
    function fn (){
        console.log(a); // undefined
        var a  = 11;
        console.log(a); // 11
    }
    fn()
    console.log(a); // 10
    相当于
    var a = 10; // 全局变量
    function fn (){
        var a; // 局部变量
        console.log(a); // undefined;
        var a  = 11;
        console.log(a); // 11;
    }
    fn()
    console.log(a); // 10
    • 理解上下文和作用域

    上下文作用域是两个不同的概念,有时我自己也经常混淆,把它们视为是同一个东西,我们知道函数的每次调用都会有与之紧密相连的作用域和上下文,从本质上说,作用域其实是基于函数的,而上下文基于对象的,也就是说作用域是涉及到它所被调用函数中的变量访问,而调用方法和访问属性又存在着不同的调用场景(4种调用场景,函数调用,方法调用,构造器函数调用,call(),apply()间接调用),而上下文始终是this所代表的,它是拥有控制当前执行代码的对象的引用

     

    • 定义一个变量到这个变量被回收做了什么

    • 进程与线程、什么是单线程?和异步有何关系

    • 理解MVVM、MVC

    • 理解AMD、commonjs

    • 虚拟内存及缓冲区溢出

    • null和undefined的区别

    • ajax/axios/fetch的区别

    • Promise的原理

    • instanceof的原理

    • typeof的原理

    • 数组的扁平化

    • xhr对象

    • ES6 Proxy的概念

    • 闭包?运行时上下文里面包括什么?

    • 结合作用域链看闭包

    • 三栏布局

    • BFC布局原理

     

     

    事件

    • even loop事件循环

         even loop总结点这里

     

    • DOM事件

    DOM的级别Level DOM0:不是W3C规范。

    DOM0事件绑定的原理
    给当前元素的某一私有属性(onXXX)赋值的过程;(之前属性默认值是null,如果我们赋值了一个函数,就相当于绑定了一个方法)
    当我们赋值成功(赋值一个函数),此时浏览器会把DOM元素和赋值的的函数建立关联,以及建立DOM元素的行为监听,当某一行为被用户触发,浏览器会把赋值的函数执行;
    DOM0事件绑定的特点:
    只有DOM元素天生拥有这个私有属性(onxxx事件私有属性),我们赋值的方法才叫事件绑定,否则属于设置自定义属性
    移除事件绑定的时候,我们只需要赋值为null;
    在DOM0事件绑定中,只能给当前元素的某一个事件行为绑定一个方法,绑定多个方法,最后一次的绑定的会替换前面绑定的

    DOM0分为两个事件:在标签内写onclick事件、在JS写onlicke=function(){}函数

    <input type="button" onclick="alert(0);" />
    
    <script>
      var btn = document.getElementsByClassName('button');
      btn.onclick = function(){
        alert(0);
      }
    </script>
    

    打印一下root,root的onclick为null

    给root添加onclick事件再打印 打印结果为fn(){}

     

    DOM1:开始是W3C规范。专注于HTML文档和XML文档。

    DOM2:对DOM1增加了样式表对象模型

    2级DOM 监听方法:addEventListener()和removeEventListener(),IE下的DOM2事件是attachEvent和 detachEvent。

    addEvenetListener()、removeEventListener() 有三个参数:
    第一个参数是事件名(如click, IE是 onclick);
    第二个参数是事件处理程序函数;
    第三个参数如果是true则表示在捕获阶段调用,为false表示在冒泡阶段调用。

    addEventListener(‘onclick’, handle):可以为元素添加多个监听事件,触发时会按照添加顺序依次调用。

    attachEvent 执行事件的顺序是从后往前的,跟addEventListener 刚好相反。

    只有2级DOM包含3个事件:事件捕获阶段处于目标阶段事件冒泡阶段, DOM0 不包含

    DOM0 与DOM2区别

    区别:

    1. 如果定义了两个dom0级事件,dom0级事件会覆盖
    2. dom2不会覆盖,会依次执行
    3. dom0和dom2可以共存,不互相覆盖,但是dom0之间依然会覆盖
    4. DOM0是私有属性赋值,DOM2是事件池的事件机制

    DOM3:对DOM2增加了内容模型 (DTD 、Schemas) 和文档验证。

    DOM3事件类型:UI事件、焦点事件、鼠标事件、滚轮事件、文本事件、键盘事件、合成事件、变动事件。

    同时DOM3级事件也允许开发人员自定义一些事件。

     

    • js事件流

    定义:"DOM2级事件"规定的事件流包括三个阶段:事件捕获阶段处于目标阶段事件冒泡阶段

    首先发生的事件捕获,为截获事件提供机会。然后是实际的目标接受事件。最后一个阶段是时间冒泡阶段,可以在这个阶段对事件做出响应。以前面的例子,则会按下图顺序触发事件。

    在DOM事件流中,事件的目标在捕获阶段不会接受到事件。这意味着在捕获阶段,事件从document到p后就定停止了。

    下一个阶段是处于目标阶段,于是事件在p上发生,并在事件处理中被看成冒泡阶段的一部分。然后,冒泡阶段发生,事件又传播回document。

     

    • js防抖和节流

    函数防抖(debounce):在事件被触发n秒后再执行回调,如果在这n秒内又被触发,则重新计时。

    场景:给按钮加函数防抖防止表单多次提交、对于输入框连续输入进行AJAX验证时,用函数防抖能有效减少请求次数。

    生活中的例子:坐电梯等。

    函数节流(throttle):规定一个单位时间,在这个单位时间内,只能有一次触发事件的回调函数执行,如果在同一个单位时间内某事件被触发多次,只有一次能生效。

    场景:游戏中的刷新率、DOM元素拖拽、Canvas画笔功能。

    生活中的例子:播放动画每一帧的频率等。

    手动实现防抖/节流点这里

     

    • 事件委托原理以及优缺点

    事件委托就是基于js的事件流产生的,事件委托是利用事件冒泡,将事件加在父元素或者祖先元素上,触发该事件。

    <body>
        <ul id="myLinks">
            <li id="goSomewhere">Go somewhere</li>
            <li id="doSomething">Do something</li>
            <li id="sayHi">Say hi</li>
        </ul>
        <script type="text/javascript">
        (function(){
            var list = document.getElementById("myLinks");
            EventUtil.addHandler(list, "click", function(event){
                event = EventUtil.getEvent(event);
                var target = EventUtil.getTarget(event);
                switch(target.id){
                    case "doSomething":
                        document.title = "I changed the document's title";
                        break;
                    case "goSomewhere":
                        location.href = "http://www.wrox.com";
                        break;
                    case "sayHi":
                        alert("hi");
                        break;
                }
            });
    
        })();
        </script>
    </body>

     上面的代码就是一个典型的事件委托案例。利用的原理就是事件冒泡,将事件加载父元素上,通过event参数来区别按钮的不同

    优点:

    1. 减少事件注册,节省内存。比如,

      • 在table上代理所有td的click事件。
      • 在ul上代理所有li的click事件。
    2. 简化了dom节点更新时,相应事件的更新。比如

      • 不用在新添加的li上绑定click事件。
      • 当删除某个li时,不用移解绑上面的click事件。

    缺点:

    1. 事件委托基于冒泡,对于不冒泡的事件不支持。
    2. 层级过多,冒泡过程中,可能会被某层阻止掉。
    3. 理论上委托会导致浏览器频繁调用处理函数,虽然很可能不需要处理。所以建议就近委托,比如在table上代理td,而不是在document上代理td。
    4. 把所有事件都用代理就可能会出现事件误判。比如,在document中代理了所有button的click事件,另外的人在引用改js时,可能不知道,造成单击button触发了两个click事件。

     

    • 回流/重绘

    回流(reflow):当DOM元素的结构或者位置发生改变都会引发回流,所谓回流,就是浏览器抛弃原有计算的结构和样式,从新进行DOM TREE或者RENDER TREE,非常非常非常...消耗性能。

    回流会从html这个根节点开始递归往下,依次计算所有可见节点的几何信息,且回流是无可避免的

    例子:容器尺寸的改变等、增加、删除 DOM节点

     

    重绘(repaint):当某一个DOM元素样式更改浏览器会重新渲染这个元素。

    例子:改变元素颜色、改变元素背景色 ……

    注意:回流一定重绘,重绘不一定回流

    关于display:none和visibility:hidden

    • display:none 的节点是不可见的,因此不会被加入Render Tree的,而visibility:hidden的节点会被加入Render Tree
    • display:none 改为 display:block 时,算是增加了一个可见节点,因此会重新渲染,所以触发回流,而visibility:hidden,节点是已经在Render Tree中的,所以会触发重绘

    解决:采用虚拟dom、集中样式更改、元素批量修改、documentFragment文档碎片

     

    浏览器相关

    • 在地址栏输入url到最终展示界面期间发生了什么

    • http、https的区别

    • 同源策略、跨域及原理

    • 缓存及更新问题

    • 新一代的前端存储方案--indexedDB

    • webview与原生应用交互

     

    DOM

    • 获取DOM节点的几个方法

    • 如何给DOM节点上添加事件

     

    服务器端知识

     

    展开全文
  • 底层原理有那么重要吗?

    千次阅读 多人点赞 2021-09-27 01:16:11
    大家好,我是贺同学。前段时间在工作业务中碰到一个技术问题, 在发现问题,思考问题,解决问题的过程中,突然对底层原理有了一些思考,这里分享一下给大家。背景在业务中使用到了 Redis 数据库...
  • 今天小编就为大家分享一篇关于HashMap和HashTable底层原理以及常见面试题,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 得遇名师,突飞猛进!iOS培训王者MJ(李明杰)老师精心研发,iOS进阶课程,实用技术不断的更新和升级,更快帮助职场人士在开发领域脱颖而出。远程视频教学,无须长途奔袭,碎片化时间学习,成长随时随地!
  • 大话存储2:存储系统架构与底层原理极限剖析》内容简介:网络存储是一个涉及计算机硬件以及网络协议/技术、操作系统以及专业软件等各方面综合知识的领域。目前国内阐述网络存储的书籍少之又少,大部分是国外作品,对...
  • SpringBoot底层原理

    2020-08-23 23:38:50
    SpringBoot底层原理一.SpringBoot是什么?二.SpringBoot核心原理 一.SpringBoot是什么? 想要了解springboot底层原理必须要先知道springboot是什么?作用是什么? SpringBoot是一个基于spring的快速开发框架,简化了...
  • 《Go语言底层原理剖析》这本书便可以帮助读者解决以上问题。 本书语言通俗易懂,书中有系统权威的知识解构、精美的示意图,并对照源码和参考文献字斟句酌,在一线大规模系统中提炼出设计哲学与避坑方法,对于编译时...
  • React底层原理

    千次阅读 2020-07-03 23:35:06
    React底层原理 1.react合成事件 react在事件处理上具有如下特点: 1.几乎所有的事件代理(delegate)到document,达到性能优化的目的 2.对于每种类型的事件,拥有统一的分发函数dispatchEvent 3.事件对象(event)是合成...
  • 《大话存储2:存储系统架构与底层原理极限剖析》适合初入存储行业的研发人员、技术工程师、售前工程师和销售人员阅读,同时适合资深存储行业人士用以互相切磋交流提高。另外,网络工程师、网管、服务器软硬件开发与...
  • 主要给大家介绍了关于iOS中id类型的理解以及底层原理的相关资料,文中介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面来一起看看吧。
  • 主要介绍了简单了解SPRINGIOC的底层原理演变过程,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 计算机网络底层原理分析详解

    千次阅读 2020-09-05 11:29:56
    DNS协议底层依赖UDP协议,udp首部较小,4个字段,8个字节:包含源端口(本机随机生成的一个端口) 和 目的端口(53号端口)。 传输层依赖于下层的网络层,网络层将数据进一步打包,打包成一个IP报文,会加上ip首部:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 450,366
精华内容 180,146
关键字:

底层原理