Java数据结构与算法初级篇之数组、集合和散列表

Java数据结构与算法初级篇之数组、集合和散列表> 数据是基础，算法是灵魂

本文出自门心叼龙的博客，属于原创类容，转载请注明出处。https://blog.csdn.net/geduo_83/article/details/86385566

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析

1. 前言
2. 数组
2.1 概念
2.2 特点
2.3 存储结构
2.4 使用场景
2.5 相关算法
3. 集合
3.1 概念
3.2 特点
3.3 适用场景
3.4 相关算法
3.5 性能分析
4. 散列表
4.1 概念
4.2 哈希算法
4.3 哈希冲突
4.4 存储结构
4.5 特点
4.6 适用场景
4.7 性能分析
5. 小结

****1. 前言****

之前没有写过关于数据结构的文章，那么今天我们将在本文中介绍最基础、最简单的数据结构。

数组，作为数据结构中最基础的一个存储方式，是我们学习一切数据结构、算法的基石。大部分的数据结构可以用数组来实现。接下来我们会介绍数组的概念、存储结构、特点和使用场景。

集合算是升级版的数组，在本文当中我们会介绍集合的概念、特点、实现以及的它的适用场景。

散列表又叫哈希表，在很多语言中都是在数组的基础上实现的，当然散列表也有其他的实现形式，本文我们会介绍散列表的基本概念、特点、实现方式等。

****2. 数组****

****2.1 概念****

数组是内存中有序的元素序列

****2.2 特点****

定长、按顺序访问、索引快、插入删除慢

****2.3 存储结构****

[图片上传失败...(image-f51670-1553424312385)]

image.gif

​[图片上传失败...(image-1f1cb-1553424312387)]

image.gif

​

****2.4 使用场景****

数组其实是非常简单的一个数据结构，用起来也比较简单，他是其他所有数据结构的基础，所以只有掌握好数组，才能学习好其他的数据结构和算法。

什么时候使用数组，通过数据的特点我们就可以想到，数据的长度是固定的，所以不会出现长度变化的业务上比较适合使用数组

如果我们在app开发中非常常见的菜单按钮，它的个数一般都是固定的不会发生变化，如下图这个界面有首页、报表、消息、我的，我们就可以用数组来存储。

[图片上传失败...(image-c4b201-1553424312385)]

image.gif

​[图片上传失败...(image-fa42a-1553424312387)]

image.gif

​

****2.5 相关算法****

****2.5.1 冒泡排序****

通过相邻的两个数两两相比来进行排序，其中有两个循环，第一个循环控制循环的轮次，第二个循环控制每一个轮次循环的次数，第一轮循环确定的最后一个元素，第二轮循环确定的是倒数第二个元素，照这样下去，直到确定了第一个元素，则循环排序完毕。

需要注意的是，第一个循环它的结束条件是i < len-1; 第二个循环的结束条件是j < len - i - 1;

package A数组.A001冒泡排序;

/**
 * Description: <冒泡排序><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] arg) {
    int[] arr = {1, 3, 10, 1, 34, 5, 21};
    sortBubbling(arr);
    int i = 0;
    while (i < arr.length) {
      System.out.println(arr[i]);
      i++;
    }
  }

  // 冒泡排序：两个循环，通过两两相比，进行排序
  private static void sortBubbling(int[] arr) {
    // 第一轮确定最后一个，第二轮确定倒数第二个...
    for (int i = 0; i < arr.length - 1; i++) {
      for (int j = 0; j < arr.length - i - 1; j++) {
        // 两两相比，就像鱼吐水泡一样...
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = temp;
        }
      }
    }
  }
}
image.gif

****2.5.2 选择排序****

第一步拿出第一个元素和剩余的元素进行比较，确定了第一个元素，第二步拿出第二个元素和剩余元素进行比较，确定了第二个元素，照这样下去，直到确定了最后一个元素，则循环排序完毕。和冒泡排序一样，也是通过两个循环来完成的，第一个循环是控制循环的轮次，第二个循环是控制每一轮循环的次数。

需要注意的是，第一个循环它的结束条件是i < len-1和冒泡排序一样，第二个循环的开始条件是j = i + 1; 结束条件是j < len 。

通过分析我们不难得出结论，无论是冒泡排序还是选择排序，第一个控制轮次的循环的结束条件都是一样的都是len - 1; 第二个控制每一轮循环次数的条件是相反的，冒泡排序控制的是结束条件j < len - i - 1，而选择排序控制的是开始条件j = i + i。

这是我们哲学中讲的矛盾，而冒泡和选择就是我们矛盾的两个方面。

package A数组.A002选择排序;

/**
 * Description: <选择排序><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] arg) {
    int[] arr = {1, 3, 10, 1, 34, 5, 21};
    sortChange(arr);
    int i = 0;
    while (i < arr.length) {
      System.out.println(arr[i]);
      i++;
    }
  }

  // 选择排序，选择第一个元素和剩下的n-1个比较
  private static void sortChange(int[] arr) {
    // 第一轮确定第一个元素，第二轮确定第二个元素
    for (int i = 0; i < arr.length; i++) {
      for (int j = i + 1; j < arr.length; j++) {
        // 选择第一i个元素和剩余的元素进行比较
        if (arr[i] > arr[j]) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
      }
    }
  }
}
image.gif

****2.5.3 桶排序****

桶排序的核心思想就是以源数组的值作为新数组的下标找到这个新元素，然后对该元素进行加1赋值。通过遍历源数组对新数组进行加1操作，一轮循环完，排序也就确定了，然后对新数组进行遍历只要发现值大于0的元素就打印它的下标，而打印的值就是我们想要的结果。

需要我们注意的是桶排序是有前提条件的必须要知道源数组中的最大元素才行，因为只有知道最大元素才能确定新数组的长度。

桶排序的效率是非常高的，但是如果源数组的值是不均匀的那么势必会造成空间的浪费，桶排序就是典型的以空间换时间的最佳范例。

package A数组.A003桶排序;

/**
 * Description: <桶排序><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] arg) {
    int[] arr = {1, 3, 10, 1, 34, 5, 21};
    sortBucket(arr);
    // int i = 0;
    // while (i < arr.length) {
    // System.out.println(arr[i]);
    // i++;
    // }
  }

  // 桶排序，声明一个以 最大元素+1 为长度的数组，遍历原数组，桶数组计数
  private static void sortBucket(int[] arr) {
    int[] arr1 = new int[34 + 1];
    for (int i = 0; i < arr.length; i++) {
      arr1[arr[i]]++;
    }
    for (int i = 0; i < arr1.length; i++) {
      int count = arr1[i];
      while (count > 0) {
        System.out.println(i);
        count--;
      }
    }
  }
}
image.gif

****2.5.4 数组中是否有重复元素****

说到元素重复我们自然会想到数组、集合，这两种数据结构都是允许重复数据的，而散列表是不允许有重复数据的。

我们想了如果我们遍历数组中的元素，把这些元素存储在散列表当中将会何如？有的人会说去重复了，是的没有错，但更重要的是我们在将数组的元素往散列表里面存入的时候加一个是否该元素在散列表中是否存在的判断不就完了吗？如果散列表中没有耶就直接存储了，如果有也就直接返回了，就这么简单。

这一招需要我们对散列表的知识非常的了解，其实对于集合和散列表都有contains这个方法。

package A数组.A004数组是否有重复元素;

import java.util.HashSet;

/**
 * Description: <数组是否有重复元素><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] arg) {
    int[] arr = {11, 3, 10, 11, 34, 5, 21};
    System.out.println(checkRepeat(arr));
  }

  // 查找一个数组里面有没有重复元素
  private static boolean checkRepeat(int[] arr) {
    // 1.声明一个散列表表
    // 2.遍历这个数组
    // 3.对遍历的元素依次进行判断，如果散列表里面没有就往散列表里面塞，有就直接退出了
    HashSet<Integer> hashSet = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
      if (hashSet.contains(arr[i])) {
        return true;
      } else {
        hashSet.add(arr[i]);
      }
    }
    return false;
  }
}
image.gif

****2.5.5 删除数组中的重复元素****

通过我们对上面判断一个数组中是否有重复元素的分析，再做这个题就非常的简单了，直接用用一个散列表就ok了。

有没有其他的解决方案？有没有不借助其他的数据结构直接就能实现的方案？有，其实方案的中心思想就是选择排序有点像，就是取出当前元素和其他剩余的元素进行对比，如果有相等的则将后面的所有元素往前移动一个位置，移动完毕在对源数组的长度进行减1的压缩处理，压缩完毕在从头开始循环判断。

这个方法就注意两点，首先只要相等就把后面的所有元素往前移位，然后移动完毕在对源数组长度进行减1的压缩处理，压缩完毕重新开始循环。

package A数组.A005删除数组重复元素;

import java.util.Arrays;

/**
 * Description: <删除数组重复元素><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAgorithm {
  public static void main(String[] arg) {
    int[] arr = {1, 3, 10, 1, 34, 5, 21};
    arr = removeRepeat(arr);
    int i = 0;
    while (i < arr.length) {
      System.out.println(arr[i]);
      i++;
    }
  }

  // 查找一个数组里面有没有重复元素，如果有则删除重复元素
  private static int[] removeRepeat(int[] arr) {
    // 取出第一个元素和剩余的其他元素进行对比
    // 一旦发现相等，则后面的元素都往前移动一个，移动完毕数组
    loop: for (int i = 0; i < arr.length; i++) {
      for (int k = i + 1; k < arr.length; k++) {
        // 如果相等则后面的元素同意往前移动
        if (arr[i] == arr[k]) {
          int head = k;
          while (head < arr.length - 1) {
            arr[head] = arr[head + 1];
            head++;
          }
          // 对数组进行压缩处理
          arr = Arrays.copyOf(arr, arr.length - 1);
          i = 0;
          // 压缩完毕，重头开始执行
          continue loop;
        }
      }
    }
    return arr;
  }
}
image.gif

****2.5.6 两数求和****

说到两数之和，那么就会想到数组中的任意两个元素都会碰一下求和和我们的目标数对比一下如果相等就把这两个元素的下标返回，这就把问题解决了。

任意两个元素都要碰一下，此时我们又想到了选择排序，通过这个算法我们就能实现两两相碰。两个循环一个判断就能问题解决。

还有另外一种算法，首先我们可以新建一个新的数据对象，还对象有两个字段，一个存下标，一个存元素的值，接着通过源数组建立一个以新数据对象为元素的数组并对该数组进行排序，然后声明两个指针，一个头指针，一个尾指针，这两个指针分别从数组的头和尾进行前进移动和回退移动，每移动一步求和，和目标数进行对比，如果小于目标数则头指针往前移动，然后再求和对比，如果大于目标数则尾指针回退移动再求和对比，直到相等就将两个对象的下标返回就解决问题了。

这两种算法各有优劣，方案1当然代码量最少是最简单的，方案2让我们感受到了指针在运算中神奇作用，虽然代码量有些大，但是思路还是很清晰的。

package A数组.A006两数求和;

import java.util.Arrays;

/**
 * Description: <><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] args) {
    int[] arr = {1, 23, 12, 2, 11, 22};
    int[] res = get(arr, 33);
    System.out.println(Arrays.toString(res));
  }
  static class Data implements Comparable<Data>{
    int index;
    int data;

    public Data(int index, int data) {
      this.index = index;
      this.data = data;
    }

    @Override
    public int compareTo(Data o) {
      return data - o.data;
    }

    @Override
    public String toString() {
      return "Data{" + "index=" + index + ", data=" + data + '}';
    }
  }
  // 指定一个目标数，查找其中两个数之和等于目标数的下标
  public static int[] get(int[] arr, int sum) {
    int[] result = {0, 0};
    // 1.首先对原数组排序
    Data[] arr1 = new Data[arr.length];
    int i = 0;
    while( i < arr.length){
      arr1[i] = new Data(i,arr[i]);
      i++;
    }

    Arrays.sort(arr1);
    System.out.println(Arrays.toString(arr1));
    // 2.声明两个指针，head，tail
    int head = 0;
    int tail = arr.length - 1;
    while (head < tail) {
      if ((arr1[head].data + arr1[tail].data) == sum) {
        result[0] = arr1[head].index;
        result[1] = arr1[tail].index;
        return result;
      } else if ((arr1[head].data + arr1[tail].data) < sum) {
        head++;
      } else {
        tail--;
      }
    }
    return null;
  }
}
image.gif

****2.5.7 求从左上到右下的路径数****

这道题大意是这样的，已知给定了一个m*n的二维数组，以第一个元素作为开始点，以最后一个元素作为结束点，然后开始点开始移动，并且只能往右往下移动直到到达结束点，求一共有多少条路径数？

看到这道算法题想必有很多人都会懵圈，真是老虎吃天无从下手，这背后到底有什么样的逻辑关系？会用到哪些数据结构？用到什么样的循环？用到什么样的判断？

其实具体的思路是这样的，声明一个m*n的二维数组，初始化赋值都为0，接着给数组的第一行赋值为1，然后给数组的第一列赋值为1，最后一步给数组中剩余的其他所有元素赋值，其他元素的值为它正上方元素的值和它正左方元素的值之和，赋值完成之后最后一个元素arr[m-1][n-1]的值就是我们所要计算的路径数，一脸懵逼，为什么？为什么通过这样的赋值就是我们想要的计算结果路径数？其实这就是算法中动态规划的问题。

我们把第一行个第一列都赋值为1，为什么？，如果只有一行或只有一列这两种情况都只有一条路，因此赋值为1没毛病，这是合乎逻辑的，然后我们开始移动，每走一步无外乎有两种方案，要么往前走，要么往下走，那么走到当前格子就有两种方案，而这个值正是它正上方元素和正左方元素的和，那么同样道理其他格子的值以此类推，而最后一个元素arr[m-1][n-1]的值就是我们所要计算的路径数。

这就是动态规划其中的奥妙之处，通过三个循环简简单单的解决了我们的问题。

package A数组.A007左上到右下路径数;

/**
 * Description: <在一个m*n的矩形方格中， 机器人在最左上的格子里，一次只能挪动一步，只能往右往下移动 目标地点在最右下方的方格里，问共有几条路径 ><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/23<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] args) {

    int path = getPath(3, 3);
    System.out.println(path);
    int[][] arr = new int[2][3];
    System.out.println("length:"+arr.length);
  }

  // 动态规划问题
  public static int getPath(int m, int n) {
    int[][] arr = new int[m][n];
    // 将第一行都赋值为1
    for (int i = 0; i < n; i++) {
      arr[0][i] = 1;
    }
    // 将第一列都赋值为1
    for (int i = 0; i < m; i++) {
      arr[i][0] = 1;
    }
    // 给其他单元格赋值
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
      }
    }
    return arr[m - 1][n - 1];
  }
}
image.gif

****2.5.8 求左上到右下的路径最小值****

这个问题是上面求路径数问题的扩展，求最小路径数，不同的是现在还是一个m*n的二维数组，不过这个数组每个元素都已经赋值了，让你求路径上所有元素的和的最小值，从左上到右下的路径有n多条，但是肯定有一条的和值是最小的。其实这还是一个动态规划的问题。

具体解决思路如下，首先声明一个大小完全相同二维数组，现在要给其赋值，赋值完毕我们要的结果也就出来了，第一个元素的值就是源数组第一个元素的值，第一行其他元素的值就是当前元素的前导元素的值和源数组这个位置元素的值的和，第一列其他元素的值就是他的前导元素的值与源数组这个位置元素的值的和，然后其他元素的值就是当前元素上方元素和左方元素取最小值和源数组这个位置元素的值求和，其他元素得计算方式以此类推，直到赋值完成，而最后一个元素的值就是我们要计算的左上到右下路径的最小值。

通过分析我们不难发现，不管是求路径数，还是求路径的最小值，其背后的核心思想都是动态规划。通过对数组的动态的赋值计算，从而得到我们要计算的结果。

package A数组.A008左上到右下路径中的最小值;

/**
 * Description: <在一个m*n的矩形方格中， 机器人在最左上的格子里，一次只能挪动一步，只能往右往下移动 目标地点在最右下方的方格里，问共有几条路径，求路径中的最小值><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/23<br>
 * Version: V1.0.2<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] args) {
    int[][] grid = new int[][] {{1, 1, 8}, {3, 1, 4}, {6, 2, 1}};
    int minvalue = getMinvalue(grid);
    System.out.println(minvalue);
  }

  private static int getMinvalue(int[][] grid) {
    int[][] result = new int[grid.length][grid[0].length];
    // 给result[0][0]赋值
    result[0][0] = grid[0][0];
    // 给第一行赋值
    for (int i = 1; i < result[0].length; i++) {
      result[0][i] = result[0][i - 1] + grid[0][i];
    }
    // 给第一列赋值
    for (int i = 1; i < result.length; i++) {
      result[i][0] = result[i - 1][0] + grid[i][0];
    }
    // 给其他元素赋值
    for (int i = 1; i < result.length; i++) {
      for (int j = 1; j < result[0].length; j++) {
        result[i][j] = Math.min(result[i - 1][j], result[i][j - 1]) + grid[i][j];
      }
    }
    return result[result.length - 1][result[0].length - 1];
  }
}
image.gif

****3. 集合****

****3.1 概念****

大家知道数据的致命缺点就是长度固定，如果我们要存储的数据长度不固定，该怎么办？这时候就要用集合了，其实集合也是基于数组实现的，不过它是一个变长数组，想放入多少就可以放入多少。集合就是一个变长数组或者叫做动态数组。

****3.2 特点****

1.它的长度是可变的

2.他会浪费一定内存空间

3.数据的拷贝会浪费一定的时间

****3.3 适用场景****

集合的适用场景非常多，如果博客的文章列表、评论列表等，只要有列表就有集合的身影。

image
image.gif

​

****3.4 常见的算法****

****3.4.1 自定义实现一个集合****

集合我们知道他是一个变长数组，只有变长才能源源不断的往里面存放数据，通过集合元素添加流程图我们也能看到，首先需要初始化一个数组，然后在添加元素的时候如果源数组满了就需要扩容了，当然扩容的系数有的是2倍，有的是0.75倍，这由自己定，不管是数组的扩容还是压缩都用到了数组工具类中非常重要的一个方法Arrays.copy(),有了添加的方法，必然少不了删除方法，删除的思路也很简单，就是把要删除的元素之后的元素都往回移动一位，然后再把最后一个元素赋值为0再退出循环就ok了。

现在我们不妨画个流程图方便大家理解集合的工作原理：

image
image.gif

​

代码实现如下：

package B集合.A001自定义实现一个ArrayList;

import java.util.Arrays;

/**
 * Description: <自定义实现一个ArrayList><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/19<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MyArrayList {
  private int[] arr;
  private int initsize = 5;
  private int size = 0;

  public MyArrayList() {
    arr = new int[initsize];
  }

  public int get(int index) {
    return arr[index];
  }

  public boolean add(int value) {
    // 说明此时数组已经满了，要扩容了
    if (size == arr.length) {
      System.out.println("数组要扩容了...");
      arr = Arrays.copyOf(arr, size * 2);
    }
    arr[size++] = value;
    return true;
  }

  public boolean remove(int value) {
    if (arr.length > 0) {
      loop: for (int i = 0; i < arr.length; i++) {
        if (arr[i] == value) {
          int temp = i;
          while (temp < arr.length - 1) {
            arr[temp] = arr[temp + 1];
            temp++;
          }
          arr[--size] = 0;
          break loop;
        }
      }
    }
    return true;
  }

  public int size() {
    return size;
  }
}
image.gif

****3.4.2 删除集合中的偶数****

很多初学者看到这个问题都觉的太简单了，不就一个循环就解决问题了吗？其实这是有大问题的，问什么？你想了循环开始的时候循环结束的条件就已经确定了，如果你在循环的过程中删除了一个元素，那么数组长度就变短了，而我们循环并没有停止，当循环走到最后的时候势必会造成数组下标越界的空指针异常，怎么办？其实我们通过集合迭代器来做这个删除的工作就可以完美的规避这个问题。因为迭代器不需要下标，也就不存在数组下标越界的问题。

package B集合.A002删除集合中的偶数;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * Description: <删除集合中的偶数><br>
 * Author: 门心叼龙<br>
 * Date: 2018/11/21<br>
 * Version: V1.0.0<br>
 * Update: <br>
 */
public class MainAlgorithm {
  public static void main(String[] arg) {
    ArrayList<Integer> list = new ArrayList() {
      {
        add(1);
        add(2);
        add(3);
        add(4);
      }
    };
    removeEvenNumber(list);
    int i = 0;
    while (i < list.size()) {
      System.out.println(list.get(i));
      i++;
    }
  }

  // 删除集合中的偶数元素
  private static void removeEvenNumber(ArrayList<Integer> myArrayList) {
    Iterator<Integer> iterator = myArrayList.iterator();
    while (iterator.hasNext()) {
      Integer next = iterator.next();
      if (next % 2 == 0) {
        iterator.remove();
      }
    }
  }
}
image.gif

****3.5 性能分析****

在算法中，每种算法的性能指标一般都有两个，即时间复杂度和空间复杂度。

时间复杂度：它定量的描述了该算法的运行时间。常常用大写的O表示。

空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的度量。

虽然集合这个变长数组比普通的数组高级一些，但是本质上它还是基于数组实现的，所以它和数组的性能差不多。

对于数组的操作，并不像我们看到的那么直观，计算机需要根据我们具体操作的位置，从头到尾一个一个地寻找到指定的位置，所以我们在数组中增加元素、修改元素、获取元素等操作的时间复杂度都为O(n)。

变长数据也有性能损耗的问题，如果插入的元素发现其中固定的数组的长度不够，则需要建立一个新的更长的数组，还要拷贝元素到新的数组，这都会造成性能损耗。

****4. 散列表****

****4.1 概念****

前面我们讲了数组和集合，他们都有一个共同的特点，他们在内存中的存储顺序是有序的，如果数据量很大我们需要在数组或者集合中查找一个元素，或者在数组或集合的头部添加或者删除一个元素，它的性能就会大大降低。

此时散列表就应运而生了，散列表是一种以空间换时间的数据结构。

让我们想一下，若在手机的通信录中查找一个人，那我们应该不会从第1个人一直的查找下去，因为这样实在是太慢了。我们其实是这样做的：首先看这个人的名字的首字母是什么，比如姓赵，那么我们会点击字母z，列表里以字母z开始的人名都会迅速的查找出来，就很快的查找到我们要查找的那个人。

还有我们在查字典的时候，需要查找一个单词，肯定不会从头翻到尾，而是通过这字的首字母，查找到对应的那一页，这样可以速度的跳到那个字所在的页面。

其实这里就用到了散列表的思想。

散列表又叫哈希表，能通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，通过关键字映射到一个表中的位置来直接访问记录，以加速访问的速度。

而这个关键字就是我通常所说的key，把对应的记录称为value，所以可以说也是通过这个key访问一个映射表来得到value的值，而这个映射表就是所说的散列表，也叫哈希表。

****4.2 哈希算法****

刚才我们说到，通过关键字映射到一个表中的位置来直接访问记录，这个映射到表中的位置就是通过哈希算法来实现的，目前这个哈希算法的实现的方法比较多，主要有以下一种：

1.直接寻址法

2.数字分析法

3.平方取中法

4.随机数法

5.除留取余法

****4.3 哈希冲突****

会有这样一种情况，有多个不同的Key通过哈希函数可能会得到相同的地址，这样就会造成对数据的覆盖、丢失。那么解决哈希冲突的处理方式也有很多种，主要有以下几种方法：

1.开放地址法

2.再哈希法

3.链接地址法

****4.4 存储结构****

一个好的散列表设计，除了需要选择一个性能较好的哈希函数，还要选择一个好的冲突解决方式。这里我们选择除留取余法作为哈希算法，选择链接地址法作为冲突的处理方式。

image
image.gif

​

****4.5 特点****

散列表有两种用法，一种是key的值和Value的值一样，一般我们称这种数据结构为Set集合；如果Key的值和Value的值不一样，我们称这种情况为Map。

1.增啥改查的速度都很快

2.无序

****4.6 适用场景****

1.数据缓存

2.快速查找

****4.7 性能分析****

散列表的访问，如果没有碰撞，那么我们完全可以认为对元素的访问的时间复杂度为O(1)

但是实际上不可能没有碰撞，Java中使用链表来解决，而碰撞之后的访问需要遍历链表，所以时间的复杂度将变为O(L),其中L为链表的长度。

****5. 小结****

数组，作为数据结构中最为基础的、常用的一个结构。而集合与散列表他们都是在数组的基础上进行稍微高级点的扩展的数据结构，通过对比这三种数据结构，我们更加清楚他们之间的区别和应用场景了，对数组的应用有了更加深入的理解。

源码下载地址：https://download.csdn.net/download/geduo_83/10913510

初级篇：Java数据结构与算法初级篇之数组、集合和散列表
中级篇：Java数据结构与算法中级篇之栈、队列、链表
高级篇：Java数据结构与算法高级篇之树、图

理论篇：Java数组、集合、散列表常见算法浅析
理论篇：Java栈、队列、链表常见算法浅析
理论篇：Java树、图常见算法浅析

问题反馈

有任何问题，请在文章下方留言。

关于作者

  var geduo_83 = {
    nickName  : "门心叼龙",
    site : "http://www.weibo.com/geduo83"
  }
image.gif
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,332评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,508评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,812评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,607评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,728评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,919评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,071评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,802评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,256评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,576评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,712评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,389评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,032评论 3赞 316
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,798评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,026评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,473评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,606评论 2赞 350

推荐阅读更多精彩内容

  • 你我的使命
    生下来、活下去。皮囊里装的使命是：工作。 我的理解。 什么是人生？作为发展到食物链顶端的我...
    龙女快跑阅读 292评论 2赞 0
  • 情感暴力
    夏末花开 ——· 关于本书 ·—— 《情感暴力》为我们讲述了在生活中如何认识与摆脱情感暴力。作者运用自己的专业知识...
    夏末花开阅读 1,630评论 0赞 2