牛客网Java刷题知识点之数组、链表、哈希表、 红黑二叉树

简介:

 首先来说一个非常形象的例子,来说明下数组和链表。


上体育课的时候,老师说:你们站一队,每个人记住自己是第几个,我喊到几,那个人就举手,这就是数组
老师说,你们每个人记住自己前面的人和后面的人,然后老师只知道第一人是谁。 然后你们各自由活动,老师要找某一个人,是不是每次都是从第一个开始往自己身后的人开始传达?这就是链表
老师说: 大家1,2,3,4报数,凡是报1,为1队,凡是报2的为2队.......  这就是散列(哈希)。而这个4就相当于预定义好的桶的个数。

 

程序中,存放指定的数据最常用的数据结构有两种:数组和链表。

 


数组和链表的区别:
1、  数组是将元素在内存中连续存放。
      链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。
2、  数组必须事先定义固定的长度,不能适应数据动态的增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费; 
链表动态地进行存储分配,可以适应数据动态地增减的情况。
3、(静态)数组从栈中分配空间,对于程序员方便快速,但是自由度小;
链表从堆中分配空间,自由度大但是申请管理比较麻烦。

 


数组和链表在存储数据方面到底谁好?根据数组和链表的特性,分两种情况讨论:
1、当进行数据查询时,数组可以直接通过下标迅速访问数组中的元素。
     而链表则需要从第一个元素开始一直找到需要的元素位置
        显然,数组的查询效率会比链表的高。

  2、当进行增加或删除元素时,在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。

             同样,如果想删除一个元素,需要移动大量去填掉被移动的元素,而链表只需改动元素中的指针即可实现增加或删除元素。

 

 


  那么哈希表,是既能具备数组的快速查询的优点,又能融合链表方便快捷的增加删除元素的优势。
所谓的hash,简单的说就是散列,即将输入的数据通过hash函数得到一个key值,输入的数据存储到数组中下标的key值的数组单元中去。 

 

 

 

 

  Java中数据存储方式最底层的两种结构,一种是数组,另一种就是链表。

  数组的特点:连续空间,寻址迅速,但是在删除或者添加元素的时候需要有较大幅度的移动,所以查询速度快,增删较慢。

  而链表正好相反,由于空间不连续,寻址困难,增删元素只需修改指针,所以查询慢、增删快。

  有没有一种数据结构来综合一下数组和链表,以便发挥他们各自的优势?答案是肯定的!就是:哈希表

  哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我们可以理解为“链表的数组”,如下图:

  哈希表。如拿HashMap来说。

 

  从上图中,我们可以发现哈希表是由数组  +   链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。它的内部其实是用一个Entity数组来实现的,属性有key、value、next。


本文转自大数据躺过的坑博客园博客,原文链接:http://www.cnblogs.com/zlslch/p/7635822.html,如需转载请自行联系原作者

相关文章
|
25天前
|
存储 Java 索引
Java快速入门之数组、方法
### Java快速入门之数组与方法简介 #### 一、数组 数组是一种容器,用于存储同种数据类型的多个值。定义数组时需指定数据类型,如`int[]`只能存储整数。数组的初始化分为静态和动态两种: - **静态初始化**:直接指定元素,系统自动计算长度,如`int[] arr = {1, 2, 3};` - **动态初始化**:手动指定长度,系统给定默认值,如`int[] arr = new int[3];` 数组访问通过索引完成,索引从0开始,最大索引为`数组.length - 1`。遍历数组常用`for`循环。常见操作包括求和、找最值、统计特定条件元素等。
|
25天前
|
存储 Java 索引
Java基础(六):数组
Java基础(六):数组
Java基础(六):数组
|
23天前
|
存储 Java C++
Java数组:静态初始化与动态初始化详解
本文介绍了Java中数组的定义、特点及初始化方式。
54 12
|
2月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
3月前
|
存储 设计模式 SQL
[Java]知识点
本文涵盖Java编程中的多个知识点,包括静态与动态代理、基本数据类型转换、设计模式、异常处理、类加载、序列化、ORM框架、IPv4地址分类、编译与解释等。文章详细介绍了每个知识点的原理和使用方法,并提供了相关示例和注意事项。
61 16
[Java]知识点
|
3月前
|
网络协议 Java 物联网
Java网络编程知识点
Java网络编程知识点
74 13
|
4月前
|
存储 缓存 算法
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
47 4
|
4月前
|
存储 缓存 算法
提高 Java 数组性能的方法
【10月更文挑战第19天】深入探讨了提高 Java 数组性能的多种方法。通过合理运用这些策略,我们可以在处理数组时获得更好的性能表现,提升程序的运行效率。
60 2
|
4月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
124 2
|
3月前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
34 0