`

第17章容器深入研究

 
阅读更多
1.List接口的相关方法
1)toArray

Object[] toArray()

    Returns an array containing all of the elements in this list in proper sequence. Obeys the

general contract of the Collection.toArray method.

2)toArray

<T> T[] toArray(T[] a)

    Returns an array containing all of the elements in this list in proper sequence; the runtime

type of the returned array is that of the specified array. Obeys the general contract of the

Collection.toArray(Object[]) method.

    Parameters:
        a - the array into which the elements of this list are to be stored, if it is big enough;

otherwise, a new array of the same runtime type is allocated for this purpose.
    Returns:
        an array containing the elements of this list.

3)set

E set(int index,
      E element)

    Replaces the element at the specified position in this list with the specified element

(optional operation).

    Parameters:
        index - index of element to replace.
        element - element to be stored at the specified position.
    Returns:
        the element previously at the specified position.
4)clear

void clear()

    Removes all of the elements from this list (optional operation). This list will be empty after

this call returns (unless it throws an exception).


5)removeAll

boolean removeAll(Collection<?> c)

    Removes from this list all the elements that are contained in the specified collection

(optional operation).

    Parameters:
        c - collection that defines which elements will be removed from this list.
    Returns:
        true if this list changed as a result of the call.

2.HashSet为快速查找而设计的Set,存入HashSet的元素必须定义hashCode()
  TreeSet保持次序的Set,底层为树结构,必须实现Comparable接口
  LinkedHashSet,具有HashSet的查询速度,且内部维护元素的出入次序。

3.Map的实现

public class AssociativeArray<K, V> {
private Object[][] pairs;
private int index;

public AssociativeArray(int length) {
pairs = new Object[length][2];
}

public void put(K key, V value) {
if (index >= pairs.length)
throw new ArrayIndexOutOfBoundsException();
pairs[index++] = new Object[] { key, value };
}

@SuppressWarnings("unchecked")
public V get(K key) {
for (int i = 0; i < index; i++)
if (key.equals(pairs[i][0]))
return (V) pairs[i][1];
return null; // Did not find key
}

public String toString() {
StringBuilder result = new StringBuilder();
for (int i = 0; i < index; i++) {
result.append(pairs[i][0].toString());
result.append(" : ");
result.append(pairs[i][1].toString());
if (i < index - 1)
result.append("\n");
}
return result.toString();
}

public static void main(String[] args) {
AssociativeArray<String, String> map = new AssociativeArray<String, String>(
6);
map.put("sky", "blue");
map.put("grass", "green");
map.put("ocean", "dancing");
map.put("tree", "tall");
map.put("earth", "brown");
map.put("sun", "warm");
try {
map.put("extra", "object"); // Past the end
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("Too many objects!");
}
System.out.println(map);
System.out.println(map.get("ocean"));
}
}
上面的代码只是说明性的,而且大小还固定,要和真正的Map比起来效率差很多。

4.散列码与散列

Object的hashCode()方法生成的散列码,默认是根据对象的地址计算出的散列码。即,如果一个类不重写该方法

,那么由该类生成的不同对象的散列码是不同的。

Object的equals()方法默认比较的是对象的地址。且正确的equals方法必须满足5个条件
1)自反行。对任意x,x.equals(x)一定返回true
2)对称性。对任意的x.equals(y)那么y.equals(x)也成立
3)传递性。x.equals(y),y.equals(z),x.equals(z)
4)一致性。如果返回true,那么不管调用任意多次都返回true
5)对任何不是null的x,x.equals(null)一定返回false.

如果要使用自己创建的类作为Map的键,必须同时覆盖equals和hashCode方法。

5.线性查询方式是最忙的查询方式。

6.区别
1)、equals方法用于比较对象的内容是否相等(覆盖以后)

2)、hashcode方法只有在集合中用到

3)、当覆盖了equals方法时,比较对象是否相等将通过覆盖后的equals方法进行比较(判断对象的内容是否相等)。

4)、将对象放入到集合中时,首先判断要放入对象的hashcode值与集合中的任意一个元素的hashcode值是否相等,如果不相等直接将该对象放入集合中。如果hashcode值相等,然后再通过equals方法判断要放入对象与集合中的任意一个对象是否相等,如果equals判断不相等,直接将该元素放入到集合中,否则不放入

总结:同一个类不同对象的散列码可能相同,可能不同,相同对象的散列码一定相同

7.通过key对象生成一个数字,将其作为数组的下标,这个数字就是散列码。该散列码由hashCode方法自动生成。为了解决数组容量被固定的问题,不同的键对象可以生成相同的散列码,这样数组大小就不是问题了。如果散列码有冲突,再用线性方式比较,因为经过散列后,相同散列码上的线性序列已经很小了,这比一开始就用线性搜索要快的多,这就是HashMap速度快的原因。

public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
// Choose a prime number for the hash table
// size, to achieve a uniform distribution:
static final int SIZE = 997;
// You can't have a physical array of generics,
// but you can upcast to one:
@SuppressWarnings("unchecked")
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];

public V put(K key, V value) {
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null)
buckets[index] = new LinkedList<MapEntry<K, V>>();
LinkedList<MapEntry<K, V>> bucket = buckets[index];
MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
while (it.hasNext()) {
MapEntry<K, V> iPair = it.next();
if (iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair); // Replace old with new
found = true;
break;
}
}
if (!found)
buckets[index].add(pair);
return oldValue;
}

public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null)
return null;
for (MapEntry<K, V> iPair : buckets[index])
if (iPair.getKey().equals(key))
return iPair.getValue();
return null;
}

public Set<Map.Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null)
continue;
for (MapEntry<K, V> mpair : bucket)
set.add(mpair);
}
return set;
}

public static void main(String[] args) {
SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
m.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("ERITREA"));
System.out.println(m.entrySet());
}
}

8.由散列码组成的表称为散列表,每个散列码称为“槽为”或是“桶位”;

9.对于现代的处理器而言,除法和求余数是最慢的操作。java的散列函数都使用2的整数次方。

10.如果想让对象生成的散列码在某个范围内,比如在0到5直接,那么就在原来的散列码基础上对5求余数。

11.在设计Hashcode方法时,最重要的就是同一个对象生成的散列码应该相同,否则在get的时候就无法取到该值。因此,散列码得生成不能依赖易变的数组或者是唯一性的数据。

12.hashCode方法的编写规则
1)生成散列码得速度必须快,并且有意义(即必须基于对象内容生成散列码);
2)散列码不必是独一无二的(重点关注速度,而不是唯一性);
3)散列码分布必须均匀;

怎么样编写hashCode方法,Joshua Block给出了一个基本的指导
1)给int变量result赋值非零常量,例如17;
2)给对象内每个有意义的域f,计算出一个int散列码c;
3)把计算得出的散列码合并;
例如:
public class CountedString {
private static List<String> created = new ArrayList<String>();
private String s;
private int id = 0;

public CountedString(String str) {
s = str;
created.add(s);
// id is the total number of instances
// of this string in use by CountedString:
for (String s2 : created)
if (s2.equals(s))
id++;
}

public String toString() {
return "String: " + s + " id: " + id + " hashCode(): " + hashCode();
}

public int hashCode() {
// The very simple approach:
// return s.hashCode() * id;
// Using Joshua Bloch's recipe:
int result = 17;
result = 37 * result + s.hashCode();
result = 37 * result + id;
return result;
}

}

依照上面的指导原则,大致可以生成一个均匀分布的散列码
分享到:
评论

相关推荐

    第17章 - 深入研究容器 - Collection(List,Set,Queue)的性能测试框架(单线程中)(P501)

    在深入研究Java集合框架,特别是List、Set和Queue的性能测试时,我们通常会关注它们在单线程环境中的表现...通过深入研究源码和构建测试框架,我们可以根据具体需求选择最高效的容器类型,从而优化我们的Java应用程序。

    编程思想下篇

    由于上传文件大小限制该资源为上下篇 本资源为下篇 第1章 对象导论 1.1 抽象过程 1.2 每个对象都有一个...第17章 容器深入研究 第18章 Java I/O系统 第19章 枚举类型 第20章 注解 第21章 并发 第22章 图形化用户界面

    Thinking in java4(中文高清版)-java的'圣经'

    类型信息 第15章 泛型 第16章 数组 第17章 容器深入研究 第18章 Java I/O系统 第19章 枚举类型 第20章 注解 第21章 并发 第22章 图形化用户界面 附录A 补充材料 可下载的补充材料 Thinking in C:Java的基础 Java...

    Java编程思想笔记(全)

    #### 第 17 章 容器深入研究 第十七章深入探讨了Java集合框架。本章详细讲解了Collection接口、List接口、Set接口以及Map接口的使用方法。此外,还会介绍ArrayList、LinkedList、HashSet、TreeSet、HashMap、...

    thinkinjava源码-Thinking-in-Java:ThinkingInJava源代码和练习题

    think in java 源码 Java编程思想(第四版) ...容器深入研究 第18章 Java I/O系统 第19章 枚举类型 第20章 注解 第21章 并发 第22章 图形化用户界面 水平有限,发现错误不适者,出门左拐找童主任。

    Docker容器平台应用分析报告.docx

    不久:• 17%不到一分钟• 78%不到一个小时• 89%不到一天• 95%不到一周最大的一类--27%,是在 5 到 10 分钟之间消失的容器。 本报告对 Docker 容器平台的应用进行了深入分析,揭示了五个有助于正确看待容器...

    C++Primer课后习题解答(第1~18章完整答案)完整版

    ### 第十七章 标准模板库容器 更深入地研究了STL容器的高级特性,如迭代器适配器,容器适配器(如`stack`、`queue`、`priority_queue`)。 ### 第十八章 额外主题 涵盖了异常处理、命名空间、模板元编程、以及C++11...

    Java开发详解.zip

    031504_【第15章:Java反射机制】_Java反射机制的深入研究笔记.pdf 031505_【第15章:Java反射机制】_动态代理笔记.pdf 031506_【第15章:Java反射机制】_工厂设计模式笔记.pdf 031601_【第16章:Annotation】_系统...

    九年级物理下册第十七章电磁波与现代通信二电磁波及其传播教学课件新版苏科版.ppt

    新版苏科版的《九年级物理下册第十七章电磁波与现代通信二》以生动的教学课件形式,让学生们初步了解电磁波及其传播的基础知识。 首先,我们得知道什么是电磁波。电磁波是在空间中传播的周期性变化的电磁场。它携带...

    java12章.zip

    11. **Java集合框架**:第十一章会深入研究Java集合框架的高级话题,如泛型,集合的排序,以及并发容器(如ConcurrentHashMap)。 12. **Java高级特性**:最后一章可能会讨论Java的新特性和更新,例如Java 8中的...

    c++ 编程思想 c++教程

    第十七章至第十九章:介绍了标准库,包括输入/输出流、字符串类、容器(如vector、list、set、map)、算法和迭代器等,这些都是C++程序员必备的知识。 第二十章至第二十一章:讨论了高级主题,如内存管理(包括指针...

    C++程序设计彻底研究(是code不是书)

    第17章 异常处理 17.1 异常及其特性 17.2 异常处理的基本语法 17.3 异常的处理过程 17.4 抛出enum实例作为异常对象 17.5 抛出类所定义的对象 17.6 常犯的错误 17.7 本章重点 17.8 本章练习 PARTⅢ 面向对象...

    MATLAB基础入门教程 MATLAB使用详解 第1章 MATLAB7.0安装与卸载 共5页.pptx

    #### 第17章 图形用户界面(GUI) - **组件设计**:按钮、文本框、滑块等。 - **事件响应**:用户交互行为的处理。 - **布局管理**:组件的排列方式。 #### 第18章 MATLAB 文件IO操作 - **文件读写**:读取和保存...

    WEB服务器工作机制由浅至深(9):【How Tomcat Works】第16章关闭钩子以及之后的章节简述

    【WEB服务器工作机制由浅至深(9):【How Tomcat Works】第16章 关闭钩子以及之后的章节简述】 ...通过深入研究这些章节,开发者能够更好地理解Tomcat的内部运作,从而实现更高效、更可靠的Web服务部署。

    Think in java学习笔记

    #### 第17章:容器深入研究 - **容器框架**:探讨了 Java 集合框架中各种容器的特性和使用方法。 #### 第18章:Java I/O系统 - **输入输出流**:介绍了 Java 的 I/O 流处理技术,包括文件读写、网络通信等内容。 ...

    Wrox.Professional.Microsoft.SQL.Server.2012.Integration.Services Copy.pdf

    ### 第17章:错误和事件处理 错误处理是任何数据集成解决方案的重要组成部分。本章介绍了SSIS中的错误处理机制,并提供了实用的技巧来确保SSIS包能够正确地处理异常情况。 ### 第18章:编程和扩展SSIS 除了使用SSIS...

    C++项目开发案例整合 源代码5-8章

    通过深入研究这些案例,你不仅可以巩固C++的基础知识,还能掌握如何将理论应用于实践,提升你的编程技巧和解决问题的能力。记得,实践是检验真理的唯一标准,通过亲手编写、运行和调试代码,你将在C++的世界里走得更...

    VC++2008入门经典高清英文原版

    ##### 第17章:对话框与控件的运用(第985页) 介绍了对话框窗体的设计以及各种常用控件(按钮、文本框、列表框等)的使用方法。 ##### 第18章:文档存储与打印(第1047页) 讲解了如何保存和加载文件中的数据,...

    肉品科学与技术.doc

    最后,第十三章介绍了肉类罐头加工工艺,包括罐头容器的选择、基本工艺流程,以及具体罐头产品的加工实例。 教材和参考书的选择对于深入学习至关重要。《肉品工艺学》由孔保华主编,黑龙江科技出版社出版,作为主要...

Global site tag (gtag.js) - Google Analytics