专栏首页猿人工厂猿思考系列9——一文获取隐藏逻辑挖掘办法

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

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

相信大家都使用过无数次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;
    }
}

本文分享自微信公众号 - 猿人工厂(gh_deca5a88e287),作者:山旮旯的胖子

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 猿实战08——属性库实现之属性关系绑定

    属性和属性值,看上去很不起眼,数据粒度也很小,但是正式因为数据粒度小,灵活多变,组织得当可以强有力的区分千变万化的商品。

    山旮旯的胖子
  • 猿设计6——真电商之属性的套路你了解吗

    看过上一章节相信你对电商系统的类目划分有了一个全新的认识,出去再跟人讲电商的类目,可不要上去就跟人扯,一颗树,一张表,外行看热闹,内行听门道,张牙舞爪的准备得再...

    山旮旯的胖子
  • 猿人进化系列1——换个姿势上网先

    从一个正常人类进化为一只程序猿,最常规的途径是经过几年的系统学习,成本较高,且枯燥无趣,过去一段时间,有一些初学者在问,有没有快点儿的的办法,工厂君思索良久,决...

    山旮旯的胖子
  • 数据结构--双向循环链表

    http://www.cnblogs.com/skywang12345/p/3561803.html

    未来sky
  • Java 集合框架(2)---- List 相关类解析(上)

    在上篇文章 Java 集合框架(1)— 概述 中我们从大体上看了一下 Java 中的集合框架,包括 List 、Set、Map 接口的一些介绍并且解释了一些接口...

    指点
  • 00--图解数据结构之开篇+集合基类

    张风捷特烈
  • 挑战程序竞赛系列(43):4.1矩阵 高斯消元

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

    它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

    JavaEdge
  • JDK源码分析-ArrayList分析

    花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

    汤高
  • Java 集合深入理解(6):AbstractList

    今天心情比天蓝,来学学 AbstractList 吧! ? 什么是 AbstractList ? AbstractList 继承自 AbstractCollec...

    张拭心 shixinzhang

扫码关注云+社区

领取腾讯云代金券