大话数据结构——查找

发表于 2018-10-01 | 分类于算法

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解查找。

查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

顺序表查找

顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个记性记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

/**
 * 顺序查找
 */
public class SequentialSearch {
    public int sequentialSearch(int[] array, int key){
        if(array.length>0){
            for(int i=0;i<array.length;i++){
                if(array[i]==key)
                    return i+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array=new int[]{1,3,5,4,6,8,7};
        SequentialSearch sequentialSearch=new SequentialSearch();
        int n=sequentialSearch.sequentialSearch(array,8);
        System.out.println("数8在数组中的第"+n+"个位置");
    }
}

有序表查找

折半查找

折半查找又称二分查找。它的前提是线性表中的记录必须是关键码有序（通常是从小到大有序），线性表必须采用顺序存储。
折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。时间复杂度为O(logn）

/**
 * 折半查找||二分查找
 */
public class BinarySearch {
    /**
     * 非递归实现
     */
    public int binarySearch(int[] array, int key){
        if(array.length>0){
            int low=0;
            int high=array.length-1;
            int mid;
            while(low<=high){
                mid=(low+high)/2;
                if(key<array[mid]){
                    high=mid-1;     //最高下标调整到中位下标小1位
                }else if(key>array[mid]){
                    low=mid+1;      //最低下标调整到中位下标大1位
                }
                else{
                    return mid+1;
                }
            }
        }

        return -1;
    }
    /**
     * 递归实现
     */
    public int binarySearch2(int[] array,int key,int low,int high){
        if(low<=high){
            int mid=(low+high)/2;
            if(key<array[mid]){
                return binarySearch2(array,key,low,mid-1);
            }else if(key>array[mid]){
                return binarySearch2(array,key,mid+1,high);
            }else{
                return mid+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array=new int[]{1,3,5,9,11,15};
        BinarySearch binarySearch=new BinarySearch();
        System.out.println("---------非递归实现二分查找----------");
        int n=binarySearch.binarySearch(array,11);
        System.out.println("数11在数组中的第"+n+"个位置");
        System.out.println("---------递归实现二分查找----------");
        int m=binarySearch.binarySearch2(array,11,0,array.length-1);
        System.out.println("数11在数组中的第"+m+"个位置");
    }
}

阅读全文 »

大话数据结构——栈和队列

发表于 2018-09-17 | 分类于数据结构

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解栈和队列。

栈与队列的定义

栈是限定仅在表尾进行插入和删除操作的线性表。（类似弹夹中的子弹）
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。（类似等待客服电话排队）

栈

栈本身也是一种线性表，除了删除和添加改名为pop(弹)和push(压)，抽象功能没有特别的地方。需要注意一点是java的sdk继承vector实现的stack，相关操作使用synchronized，具有安全性。

栈的顺序存储结构(顺序栈)

/**
 * 基于数组实现的顺序栈
 * @param <E>
 */
public class Stack<E> {
    private Object[] data = null;
    private Object e;
    private int maxSize=0;
    private int top=-1;

    /**
     * 构造函数：根据给定的size初始化栈
     */
    Stack(){
        this(10);
    }

    public Stack(int initSize){
        if(initSize>=0){
            this.maxSize=initSize;
            data = new Object[initSize];
            top=-1;
        }else{
            throw new RuntimeException("初始化大小不能小于0"+initSize);
        }
    }

    //判断栈是否为空
    public boolean isEmpty(){
        return top == -1 ? true : false;
    }

    //元素进栈
    public boolean push(E e){
        if (top == maxSize-1){
            throw new RuntimeException("栈已满，元素无法入栈！");
        }else{
            data[++top]=e;
            return true;
        }
    }

    //查看栈顶元素
    public Object peek(){
        if(top==-1){
            throw new RuntimeException("栈为空！");
        }else{
            return data[top];
        }
    }

    //元素出栈
    public Object pop(){
        if(top==-1){
            throw new RuntimeException("栈为空！");
        }else{
            Object elem=data[top];
            data[top--]=null;
            return elem;
        }
    }

    //返回对象在堆栈中的位置，以1为基数
    public int search(E e){
        int i=top;
        while(top!=-1){
            if(peek()!=e){
                top--;
            }else{
                break;
            }
        }
        int result = top+1;
        top=i;
        return result;
    }
    //查看栈的大小
    public int getSize(){
        return top+1;
    }

    //清空栈
    public void clear(){
        Arrays.fill(data,null);
        top=-1;
    }

    public static void main(String[] args) {
        Stack<String> stack=new Stack<>();
        System.out.println("stack.maxSize="+stack.maxSize);
        System.out.println("stack.size="+stack.getSize());
        System.out.println("stack is empty?"+stack.isEmpty());
        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");
        stack.push("e");
        System.out.println("stack.size="+stack.getSize());
        System.out.println("stack is empty?"+stack.isEmpty());
        System.out.println(stack.pop());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println("stack.size="+stack.getSize());
        System.out.println("stack is empty?"+stack.isEmpty());
        stack.clear();
        System.out.println("---------------after clear---------------");
        System.out.println("queue is empty?"+stack.isEmpty());
        System.out.println("queue.size="+stack.getSize());
    }

}

阅读全文 »

大话数据结构——串

发表于 2018-09-15 | 分类于数据结构

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解串。

串

串（string）是由零个或多个字符组成的有限序列，又名字符串。

串的存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。用“\0”来表示串的终结，不计入串长度，但是计入数组长度。两个长度不同的串不可能相等。

串的链式存储结构要考虑一个结点是存放一个字符（会造成很大的空间浪费）还是多个字符。除了链接串与串的操作有一定方便外，总的来说不如顺序存储量或，性能也不如顺序存储结构好。

朴素的模式匹配算法

串的模式匹配：串的定位操作。
时间复杂度：O(1)–最好；O(n+m)–平均；O(n-m+1)*m–最不好

阅读全文 »

大话数据结构——树

发表于 2018-09-15 | 分类于数据结构

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解树。

树

树（Tree）是n（n>=0）个结点的有限集。 n=0又称为空树。在任意一课非空的树中：有且仅有一个特定的称为跟（Root）的结点；当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树是一种一对多的数据结构。

需要注意的是：当n>0时根结点是惟一的，不可能存在多个根结点。 m>0时，子树的个数没有限制，但它们一定是互不相交的。如果相交，就不符合树的定义。

结点拥有的子树称为结点的度。度为0的结点称为叶结点或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

树中结点最大的层次称为树的深度或高度。

树的存储结构

树有两种实现方式：数组和链表；

树有三种不同表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

二叉树

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点

每个结点最多有两棵子树，所以二叉树中不存在大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。左子树和右子树是有顺序的，次序不能颠倒。就像人的左右手。即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树有5种基本形态

空二叉树。

只有一个根结点。

根结点只有左子树。

根结点只有右子树。

根结点既有左子树又有右子树。

特殊二叉树

斜树：只有左子树或者只有右子树。线性表是一种特殊的树。

满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。

满二叉树的特点有：

叶子只能在最下一层。出现在其他层就不可能达到平衡。

非叶子结点的度一定是2。否则就是“缺胳膊少腿了”。

在同样深度的二叉树中，满二叉树的结点个数越多，叶子树越多。

阅读全文 »

一致性哈希算法

发表于 2018-09-13 | 分类于服务器

一致性Hash算法背景

　　一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

　　但现在一致性hash算法在分布式系统中也得到了广泛应用，研究过memcached缓存数据库的人都知道，memcached服务器端本身不提供分布式cache的一致性，而是由客户端来提供，具体在计算一致性hash时采用如下步骤：

首先求出memcached服务器（节点）的哈希值，并将其配置到0～2^32的圆（continuum）上。
然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。

从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率，但Consistent Hashing中，只有在园（continuum）上增加服务器的地点逆时针方向的第一台服务器上的键会受到影响，如下图所示：

一致性Hash性质

　　考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其实在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效（即由于系统节点数目变少，客户端在请求某一对象时需要重新计算其hash值（通常与系统中的节点数目有关），由于hash值已经改变，所以很可能找不到保存该对象的服务器节点），因此一致性hash就显得至关重要，良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：

阅读全文 »