数据类型
数据结构：
1.基本构成
数组和链表
2.具体的数据结构
动态数组 ArrayList
队列 Queue接口作为队列数据结构 LinkedList LinkedList类实现了Queue接口和 Deque
双端队列 Deque接口（双端队列） Deque接口所能代表的数据结构：队列，双端队列，栈 ArrayDeque
栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则，将Deque限制为只能从一端入队和出队，则可实现栈的数据结构
哈希表 HashMap HashSet LinkedHashMap (顺序地去存储key-value 保存了记录的插入顺序) LinkedHashSet
排序二叉树 TreeMap TreeSet
堆-完全二叉树 PriorityQueue 优先级队列，但也是比较通用的实现了堆性质的数据结构
位向量 EnumSet 是用位向量实现的
B-tree 数据库中的索引常用-- 多路搜索树 带有顺序访问指针的B+Tree
bitMap
Map数据类型
1.Map填充数据- 一行的是一个value
其中 ： List<Row> TestRow
//步骤一: 声明变量，生成实例
Map<String ,ExpBean> setBean = new HashMap<>();
if(TestRow != null && !TestRow.isEmpty()) {
for (Row row : TestRow) {
String testCd= row.getAs("testCd").toString().toLowerCase();
// 一行数据生成一个testDataBean
ExpBean testDataBean = new ExpBean();
setBean.put(testCd,testDataBean);
}
}
2.Map填充数据- 一类的是一个value
其中 ： List<Row> TestRow
//步骤一: 声明变量，生成实例
Map<String ,ExpBean> setBean = new HashMap<>();
if(TestRow != null && !TestRow.isEmpty()) {
for (Row row : TestRow) {
String testCd= row.getAs("testCd").toString().toLowerCase();
//步骤二:containsKey 作为判断的条件
if(setBean.containsKey(testCd)) {
//提取ExpBean，并且调用ExpBean的方法
ExpBean testDataBean = setBean.get(testCd);
testDataBean.deal(row);
}else{
//不存在则生成ExpBean, 并且调用ExpBean的方法
ExpBean testDataBean = new ExpBean();
testDataBean.deal(row);
//将对应的ExpBean 实例存放到Map中去
setBean.put(testCd,testDataBean);
}
}
}
3.另外一种实现
其中 ： List<Row> TestRow
//步骤一: 声明变量，生成实例
Map<String ,ExpBean> setBean = new HashMap<>();
if(TestRow != null && !TestRow.isEmpty()) {
for (Row row : TestRow) {
String testCd= row.getAs("testCd").toString().toLowerCase();
//步骤二:先使用get来取数据，一类数据生成一个testDataBean
ExpBean testDataBean = setBean.get(testCd);
//步骤三: 判断是否为空，不为空，则代表有，是空，则代表没有，新生成相应的对象
if(testDataBean == null) {
testDataBean = new ExpBean();
setBean.put(testCd,testDataBean);
}
//步骤四： Bean对象的操作
testDataBean.deal(row);
}
}
Map遍历的实现
1.Map遍历的方式一
1.用Iterator来遍历
// 获取键值对的迭代器 Iterator<Entry<String, String>> it = strMap.entrySet().iterator();
// 获取键集合的迭代器 Iterator<String> it = strMap.keySet().iterator();
// 获取值集合的迭代器 Iterator<String> it = strMap.values().iterator();
遍历HashMap的entrySet键值对集合
1.通过HashMap.entrySet()得到键值对集合；
2.通过迭代器Iterator遍历键值对集合得到key值和value值；
eg：
Map<String, String> strMap = new HashMap<String, String>();
if(!strMap.isEmpty()) {
// 获取键值对的迭代器
Iterator<Entry<String, String>> it = strMap.entrySet().iterator();
while (it.hasNext()) {
Entry<String, String> en = it.next();
String key = en.getKey();
String stb = en.getValue();
System.out.println("key:" + key + "---" + "value:" + value);
}
}
遍历方式二
2.用for循环遍历
// strMap.entrySet() strMap.keySet() strMap.values()
//
eg:
// Set<Map.Entry<String, String>> entrySet = strMap.entrySet();//把这个set取出来
for (Map.Entry<String, String> entry : strMap.entrySet()) {/*---*/
System.out.print("key= " + entry.getKey() + " and value= " + entry.getValue() + "; ");
}
进一步的方法
/**
* @since 1.8
*/
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
forEach
putIfAbsent
merge
类定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {}
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{}
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{}
其中 SortedMap 提供排序接口
public interface NavigableMap<K,V> extends SortedMap<K,V> {
public interface SortedMap<K,V> extends Map<K,V> {}
Set
HashSet: 没有重复，且没有顺序
HashSet以及HashMap要求元素重写 hashCode和equals方法，
如果两个对象equals相同，则hashCode必须相同，自定义尤其要注意
HashSet内部是用HashMap实现的，内部有一个HashMap的实例对象 ，HashSet相当于只有键，而值是相同的
这个value值是 private static final Object PRESENT = new Object(); //固定的共享值
LinkedHashSet 介于HashSet和TreeSet之间。它也是一个hash表 --输出的顺序时确定的，就是插入的顺序。
TreeSet ：有顺序
Set<String> defineClassSet = new HashSet<>();
遍历的方法
用Iterator来遍历
Iterator<> iterator = defineClassSet.iterator();
While(iterator.hasNext()){
System.out.println( iterator.next());
}
用for循环遍历
for( String examp: defineClassSet){
System.out.println( examp);
}
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
SortedSet和SortedMap 这两个接口提供排序操作
public interface NavigableSet<E> extends SortedSet<E> {
public interface SortedSet<E> extends Set<E> {
Queue
* Java Collections Framework</a>.
*
* @see java.util.Collection
* @see LinkedList
* @see PriorityQueue
* @see java.util.concurrent.LinkedBlockingQueue
* @see java.util.concurrent.BlockingQueue
* @see java.util.concurrent.ArrayBlockingQueue
* @see java.util.concurrent.LinkedBlockingQueue
* @see java.util.concurrent.PriorityBlockingQueue
* @since 1.5
* @author Doug Lea
* @param <E> the type of elements held in this collection
*/
public interface Queue<E> extends Collection<E> {
ArrayList 以及LinkedList
List<String> list = new ArrayList<String>();
//方法1
Iterator it1 = list.iterator();
while(it1.hasNext()){
System.out.println(it1.next());
}
//方法2
for(String tmp:list){
System.out.println(tmp);
}
//方法3
for(Iterator it2 = list.iterator();it2.hasNext();){
System.out.println(it2.next());
}
//方法4
for(int i = 0;i < list.size(); i ++){
System.out.println(list.get(i));
}
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}
2.Fail-fast 机制
是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件
ArrayList中有个成员变量 modCount ，继承于AbstractList。
这个成员变量记录着集合的修改次数，也就每次add或者remove它的值都会加1
next和remove操作之前都会先调用checkForComodification来检查expectedModCount和modCount是否相等
ConcurrentModificationException 异常
重写hashCode() 以及 equal()
1.为什么要重写
hashCode()方法确定元素在数据结构中存放的位置。
Java的继承体系中，Object类是所有类的超类，
也就是说实际上自定义的类是继承了Object类的，
因此没有重写hashCode()方法，那么调用的就是Object类的hashCode()方法了
equals()
而使用equals()来确认当两个元素存放的位置发生冲突时，是应该将两个元素都存入数据结构，还是说只需要存放其中一个。
如果equals()方法判断两个元素是一样的，那么当然只需要存放其中一个既可；
但如果equals()方法判断两个对象是不同的，那么当然两个都需要存放到数据结构中。
2.怎样重写
equal()
首先判断是否是自己和自己比较，如果是那么肯定是相同的，因为是同一个对象。
然后再逐个比较对象的属性，如果属性值都相同，那么说明就是相同的对象。
例子Spark源码中Optional 重写
@Override
public int hashCode() {
return value == null ? 0 : value.hashCode();
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Optional)) {
return false;
}
Optional<?> other = (Optional<?>) obj;
return Objects.equals(value, other.value);
}
@Override
public String toString() {
return value == null ? "Optional.empty" : String.format("Optional[%s]", value);
}
Flink中的源码
@Override
public int hashCode() {
return enumClass.hashCode();
}
@Override
public boolean equals(Object obj) {
if (obj instanceof EnumSerializer) {
EnumSerializer<?> other = (EnumSerializer<?>) obj;
return other.enumClass == this.enumClass && Arrays.equals(values, other.values);
} else {
return false;
}
}
@Override
public String toString() {
return "EnumSerializer{" +
"enumClass=" + enumClass +
", values=" + Arrays.toString(values) +
'}';
}
使用场景
在重写 equals 方法的时侯，一定要重写 hashcode 方法
编程中递归
增加IF语句进行初始化
增加中间变量用于数据变换
递归函数意味着函数可以调用它本身，在满足条件的时候函数会返回。
递归-- 实现循环
1.递归的关键点
01.一个递归算法，必须要有这样一个边界条件
02. 分解和组合
用例
01.递归对于列表的一种的处理方式： 即对一个列表的操作，可转化为对第一个元素，及剩余列表的相同操作
2.过程关键点
整个递归的终止条件。 找整个递归的终止条件：递归应该在什么时候结束？
一级递归需要做什么？ 找返回值：应该给上一级返回什么信息？
应该返回给上一级的返回值是什么？本级递归应该做什么：在这一级递归中，应该完成什么任务？
3.递归的形式
01.直接递归 direct recursion -- 互递归 (trivial case).
递归算法需要保持调用堆栈，效率较低，如果调用次数较多，会耗尽内存或栈溢出，即
如果递归嵌套很深，容易出现栈溢出的问题
02.间接递归 indirect recursion
03.尾递归 tail recursion
-- 尾递归函数 Tail Recursive Function 所有递归形式的调用都出现在函数的尾部
就是最后一步是递归操作本身(即没有和其它参数参与)，
只有到达特定状态的时候, 再去构造返回结果, 而其它时候, 只需要更新一些状态变量即可
尾递归可以进行优化，将递归转换成循环实现，避免栈的溢出
4.具体语言：
Scala语言特别增加了一个注释@tailrec
@tailrec
Java
-- 递归实现字符串的反转
用例
public String reverse(String str){
if(str == null || str.length() <= 1){
return str;
}else
{
return reverse(str.subString(1)) + str.charAt(0);
}
}
参考：