猿思考系列9——一文获取隐藏逻辑挖掘办法

山旮旯的胖子

发布于 2020-07-28 16:53:48

26900

代码可运行

运行总次数：0

代码可运行

看完上一个章节，相信你已经充分的掌握了数据库事务的一些事情，猿人工厂君也知道，内容对于新手而言，理解起来还是比较很吃力的，文中提到的原理和内容，有兴趣的可以和我一起探讨，猿人工厂君就不一一赘述了。之前有小伙伴反应，数据结构的知识比较薄弱，今天我们就来探讨下，通过思考的方式，来解决基本的数据结构问题。本文是思考系列的最后一章，从下一章节开始，带你玩儿框架和实战完成猿蜕变！

相信大家都使用过无数次ArrayList了，一个大家常用的集合容器——可变数组。既然是容器，那自然是什么东西都能存放的啦。数组一般来说都是长度不变的，那要做到长度可变该怎么办呢？

开动你的小脑筋，既然要存放任何数据，那自然是Object比较可靠啦，对象之祖，可以表示仍和数据。长度可变，自然是存放满了之后，改变数组长度了。

嗯，在数组种放入数据确实简单，但是依然是有一些隐藏逻辑的。想想看，比如数组越界的处理，比如增加或删除数据后，原有数据发生移动，比如数据存放时，恰巧遇到数据满了之后，原有数据需要拷贝和移动。以上这些都是数组操作的隐藏逻辑噢，发现这些隐藏逻辑，对你的编码能力和业务分析能力的提升是很有帮助的。下面是一个简单的实现，拿走不谢噢。

package com.pz.collection.demo;
 
/**
 * pangzi
 * 模拟实现ArrayList
 */
public class ArrayList {
    //使用数组存放数据
    privateO bject[] elementData;
    //数组大小
    private int size;
 
 
    /**
     *无参构造方法 默认大小10
     */
    public ArrayList(){
 
       this(10);
    }
 
    /**
     *
     * @paraminitialCapacity
     */
    public ArrayList(int initialCapacity){
 
       if(initialCapacity<0){
           try {
               throw new Exception();
            }catch (Exception e) {
               e.printStackTrace();
            }
        }
       elementData=new Object[initialCapacity];
    }
 
    /**
     * 判断容器是否为空
     * @return
     */
    public boolean isEmpty(){
 
        return size==0;
    }
 
    /**
     * 根据下标获取元素
     * @paramindex
     * @return
     */
    public Object get(int index){
       rangeCheck(index);
        return elementData[index];
    }
 
    /**
     * 默认增加在数组尾部增加元素
     * @paramobj
     * @return
     */
    public boolean add(Object obj){
       ensureCapacity();
       elementData[size]=obj;
       size++;
        return true;
    }
 
    /**
     * 在指定下标增加元素
     * @paramindex
     * @paramobj
     */
    public void add(int index,Object obj){
       rangeCheck(index);
       ensureCapacity();
       System.arraycopy(elementData, index, elementData, index+1,size-index);
       elementData[index]=obj;
       size++;
    }
 
    /**
     * 删除指定下标元素
     * @param index
     * @return
     */
    public Object remove(int index){
       rangeCheck(index);
        int arrnums=size-index-1;
        ObjectoldValue=elementData[index];
       if(arrnums>0){
           System.arraycopy(elementData, index+1, elementData,index, arrnums);
        }
       elementData[--size]=null;
        return oldValue;
    }
 
    /**
     * 根据对象删除元素
     * @paramobj
     * @return
     */
    public boolean remove(Object obj){
       for(int i=0;i<size;i++){
           if(get(i).equals(obj)){
               remove(i);
            }
           break;
        }
        return true;
    }
 
    /**
     * 根据下标改变对象并返回旧的值
     *
     * @paramindex 下标
     * @paramobj   元素
     * @return
     */
    public Object set(int index,Object obj){
       rangeCheck(index);
        ObjectoldValue=elementData[index];
       elementData[index]=obj;
        return oldValue;
    }
 
    /**
     * 范围检查
     * @paramindex 下标
     */
    private void rangeCheck(int index){
 
       if(index<0||index>=size){
           try {
               throw new Exception();
            }catch (Exception e) {
               e.printStackTrace();
            }
        }
    }
 
    /**
     * 数组扩容检查
     */
    private void ensureCapacity(){
       if(size==elementData.length){
           Object[] newArray=new Object[size*2+1];
           System.arraycopy(elementData, 0, newArray, 0, elementData.length);
           elementData=newArray;
        }
    }
 
    /**
     * 返回元素第一次出现下标
     * 如果无元素返回-1
     * @paramobj
     * @return
     */
    public int indexOf(Object obj) {
        if(obj == null) {
           for (int i = 0; i < size; i++){
               if (elementData[i]==null){
                   return i;
}
}
 
        } else{
           for (int i = 0; i < size; i++){
               if (obj.equals(elementData[i])){
                   return i;
                }
}
        }
        return-1;
    }
 
    /**
     * 返回元素最后一次出现下标
     * 如果无元素返回-1
     * @paramobj
     * @return
     */
    public int lastIndexOf(Object obj) {
        if(obj != null) {
           for (int i = size-1; i >= 0; i--) {
               if (obj.equals(elementData[i])) {
                   return i;
               }
            }
        } else{
 
           for (int i = size-1; i >= 0; i--) {
               if (elementData[i] == null) {
                   return i;
               }
            }
        }
        return-1;
    }
 
    /**
     * 返回List大小
    * @return
     */
    public intsize(){
 
        return size;
    }
}

数组的实现已经学会了，那么数组有什么特点呢？自然是连续存储，查找效率较高，但是插入和删除因为发生数据移动的关系，效率会低一些，记住了。面试官经常问的噢。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。。

学会理解概念也是一种本事呢。指针，在java里是不存在的，但是有一个替代品——引用类型。那怎样去实现一个链表呢？自然是定义一个类，一个Object类型的属性，用于存放数据，一个next属性，引用自身，指向下一条数据就好了。这样一条数据，指向下一条数据的结构，不就像自行车链条一样吗？如果我们要做插入操作，找到需要插入的位置，改变引用的位置，插入位置的下一个节点，指向新数据，新数据的下一个节点，指向老数据的下一个节点就好了，数据不需要发生移动。删除也是一样的，找到需要删除的节点，让被删除的节点的上一个节点，指向被删除的节点的下一个节点就好了。下面是以一个简单的单向链表实现，你可以参考，也可以另行实现。

package com.pz.collection.demo;
 
/**
 * 节点
 * pangzi
 */
public class Node{
 
    public Object data;//元素
    public Node next;//指针
    public Node(Object data, Node next) {
       this.data = data;
       this.next = next;
    }
    public Node(){
       this(null,null);
    }
    public Node(Object data){
       this(data,null);
    }
 
    @Override
    public String toString() {
        return"Node [data=" + data + "]";
    }
}

package com.pz.collection.demo;
 
 
/**
 * 单链表
 */
public class LinkedList {
 
    private Node headNode;
    private int size;
    public LinkedList(){
       headNode = new Node(null,null);
        size =0;
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }
    public void addFirst(Object obj){
 
        add(0,obj);
    }
    public void addLast(Object obj){
       add(size,obj);
    }
    public void add(int index,Object obj){
       if(index < 0 || index > size){
           throw new IllegalArgumentException("索引越界异常");
        }
        Nodeprev = headNode;
       for(int i = 0 ; i < index ; i++){
           prev = prev.next;
        }
       prev.next = new Node(obj,prev.next);
        size++;
    }
    public Object get(int index){
       if(index < 0 || index > size){
            throw newIllegalArgumentException("索引越界异常");
        }
        Nodecur = headNode.next;
       for(int i = 0 ; i < index ; i++){
           cur = cur.next;
        }
        return cur.data;
    }
    public Object getFirst(){
        return get(0);
    }
    public Object getLast(){
        return get(size-1);
    }
    public void update(int index,Object obj){
       if(index < 0 || index > size){
           throw new IllegalArgumentException("索引越界异常");
        }
        Nodecur = headNode.next;
       for(int i = 0 ; i < index ; i++){
           cur = cur.next;
        }
       cur.data = obj;
    }
    public boolean contains(Object obj){
        Nodenode = headNode.next;
        while(node != null){
            if(node.data.equals(obj)){
               return true;
            }
           node = node.next;
        }
        return false;
    }
    public void delete(int index){
       if(index < 0 || index > size){
           throw new IllegalArgumentException("索引越界异常");
        }
        Nodeprev = headNode;
       for(int i = 0 ; i < index ; i++){
           prev = prev.next;
        }
        Nodecur = prev.next;
       prev.next = cur.next;
       cur.next = null;
       size--;
    }
    public void deleteFirst(){
       delete(0);
    }
    public void deleteLast(){
       delete(size-1);
    }
    public void deleteElement(Object obj){
        Nodeprev = headNode;
       while(prev.next != null){
           if(prev.next.data.equals(obj))
               break;
           prev = prev.next;
        }
       if(prev.next != null){
           Node delNode = prev.next;
           prev.next = delNode.next;
           delNode.next = null;
            size --;
        }
    }
}

相信你已经看出来了，上面的结构就是HashMap。其实最基本的数据结构从来就只有两种：连续存储的数组和非连续存储的单链表。其余所有的数据结构，都来自二者的组合。

HashMap就是这样的一个结构，一个数组，用于存放Entry，Entry通过key进行hash算法快速的定位下标，如果出现hash冲突，那么将发生冲突的节点，挂到相同hash值的Entry的后面即可。这样一来，查询找节点时通过key，进行hash计算，快速定位出元素数组里的下标，如果没有立刻找到，再遍历对应的链表就好了，插入和删除，都不需要移动元素。算法的好坏关键，就在于hash冲突的多少，越少的冲突，带来越好的性能。

下面就是一个HashMap的简单实现，你也可以尝试自己写一下。

package com.pz.collection.demo;
 
public class HashMap<K, V> {
    private int capacity = 16;
    private int size = 0;
    private Entry[] table;
 
    public HashMap(int capacity) {
       this.capacity = capacity;
       this.table = new Entry[capacity];
    }
 
    public HashMap() {
       this.table = new Entry[capacity];
    }
 
    public V put(K key, V value) {
        if(key == null) {
           return putNullKey(value);
        }
        inthash = hash(key);
        int i= indexTable(hash, capacity);
 
        for(Entry<K, V> e = table[i]; e != null; e = e.next) {
            if(e.hash == hash && (e.key == key || e.key.equals(key))) {
               V old = e.value;
               e.value = value;
                return old;
            }
        }
 
       addEntry(hash, key, value, i);
 
        returnnull;
    }
 
    public V get(K key) {
        if(key == null)
           return getNullKey();
 
        inthash = hash(key);
        int i= indexTable(hash, capacity);
 
        for(Entry<K, V> e = table[i]; e != null; e = e.next) {
            if(e.hash == hash && (e.key == key || e.key.equals(key)))
               return e.value;
        }
 
        return null;
    }
 
    private V getNullKey() {
        for(Entry<K, V> e = table[0]; e != null; e = e.next) {
            if(e.key == null)
               return e.value;
        }
        return null;
    }
 
    private void addEntry(int hash, K key, V value, int i) {
       Entry<K, V> e = table[i];
       table[i] = new Entry<K, V>(hash, key, value, e);
        if(size == capacity)
           resize();
 
       size++;
    }
 
    private void resize() {
       capacity = capacity * 2;
       Entry[] newtable = new Entry[capacity];
        for(Entry<K, V> entry : table) {
           Entry<K, V> e = entry; // 取得旧Entry数组的每个元素
            if(e != null) {
               entry = null;// 释放旧Entry数组的对象引用（循环后，旧的Entry数组不再引用任何对象）
               do {
                   Entry<K, V> next = e.next;
                   int i = indexTable(e.hash, capacity); // 重新计算每个元素在数组中的位置
                   e.next = newtable[i];
                   newtable[i] = e; // 将元素放在数组上
                   e = next; // 访问下一个Entry链上的元素
               } while (e != null);
            }
        }
        table= newtable;
    }
 
    private int indexTable(int hash, int capacity) {
        returnhash & (capacity - 1);
    }
 
    private int hash(K key) {
        if(key == null)
           return 0;
 
        int h= key.hashCode();
        h = h^ (h >>> 16);
 
        returnh;
    }
 
    private V putNullKey(V value) {
        for(Entry<K, V> e = table[0]; e != null; e = e.next) {
            if(e.key == null) {
                V old = e.value;
               e.value = value;
               return old;
            }
        }
 
       addEntry(0, null, value, 0);
 
        return null;
    }
 
}
 
class Entry<K, V> {
    public int hash;
    public K key;
    public V value;
    public Entry<K, V> next;
 
    public Entry(int hash, K key, V value, Entry<K, V> next) {
       this.hash = hash;
       this.key = key;
       this.value = value;
       this.next = next;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法