Java
Serializable 和Parcelable
Serializable 和Parcelable为Android中序列化的两种方案。Serializable 为Java提供，它可以将对象转换成可传输状态，序列化后的对象可以进行IO传输然后持久的保存在相应的地方。Parcelable为Android提供，它解决了Serializable 在内存中传递对象效率低下的问题，所以Parcelable一般是用于在内存中传递对象，比如Activity之间传递数据、通过Binder在应用程序之间传递数组。
使用方法：
Serializable 是一个没有任何方法的接口，直接用类实现即可，具体序列化和反序列化由Java帮我们实现。
Parcelable也是一个接口但有两个抽象方法需要开发者自己实现，两个方法分别是序列化过程和反序列化过程。
注意点：Serializable序列化不保存静态变量，可以使用Transient关键字对部分字段不进行序列化
equels和==、hashCode的区别
"=="：
基本数据类型：用于比较两个数据的值是否相等。
引用数据类型：比较的是堆内存中对象的地址值是否相同。
"equels"：
equels是Object类的一个方法，默认为比较对象地址值，但一些类库中都对该方法进行了重写比如String、Integer，Date，这些类中比较的是对象的值。
"hashCode"：
一个hashCode通过hash计算后会得出一个hash值，hash值不同的两个对象肯定不是同一个对象，hash值相同的对象可能是同一个对象(因为存在hash冲突的可能)
String、StringBuilder、StringBuffer区别
String：字符串常量，每次改变值都会产生新的对象。
StringBuilder：字符串变量，当频繁修改字符串时不会产生新的对象，效率高但多线程下不安全。
StringBuffer：与StringBuilder不同，StringBuffer在多线程下是安全的，但效率相比于StringBuilder要低一些。
线程创建方式
- Thread：继承Thread重写其run()方法来创建一个线程。好处是书写方便。
- Runnable：实现Runnable接口中的run()方法，将Runnable对象传入Thread中来创建一个线程。好处是可以将任务独立。
- Callable：一般需要配合Future接口使用，Future内有几个方法可以获取线程执行结果、取消线程任务。Java提供了一个FutureTask类，它实现了Runnable和Future接口。FutureTask可以接收一个Callable类型对象，在自己的run()方法中会调用Callable的call()方法，所以耗时任务封装在Callable的call()方法中即可。好处：调用FutureTask的get()方法可以获取线程执行结果，也可通过调用cancel()方法取消任务。
synchronized、volatile关键字的作用
- synchronized：在多线程领域中使用，加上synchronized关键字后其作用域内代码只能被当前线程执行，通俗一点讲就是线程A正在执行被synchronized修饰的代码，此时其他线程是不能进入执行的，需要等线程A执行完毕后其他线程才能够进入synchronized修饰域。使用synchronized时还需要配备一个锁对象，当一个线程执行同步方法或者同步代码块时需要先判断该同步锁是否正在被使用，如果正在使用就等锁释放后再执行。
- volatile：volatile是Java提供的一种轻量级的同步机制(synchronized为重量级同步机制)，合理的使用能减少很多不必要的内存开销。
wait、notify、sleep、join方法的作用
- wait()：属于Object的方法，通常在同步函数或者同步代码块中由锁对象调用，当一个线程执行到了wait()方法就会将该线程放到所对象对应的线程池中并处于冻结状态。
- notify()：与wait()方法配合使用，通常也用所对象调用，可以唤醒线程池中任意一个线程。Java也提供了唤醒一个线程池中全部线程的方法notifyAll()。
- sleep()：可以将当前线程处于冻结状态，与wait()不通sleep()可以指定睡眠时间，过了睡眠时间会自动唤醒。
- join()：当一个线程对象调用了join()方法后，调用join()方法所在的线程会等线程对象任务执行完毕后再无往下执行。
线程池
详解
线程池也是多线程的一种形式，可以将任务加入到任务队列然后由线程池中的线程执行这些任务，好处就是可以对线程进行复用，线程在Java中属于稀缺资源，所以碰到需要大量使用线程的需求可以考虑使用线程池。Java为开发者提供了四种线程池
- FixedThreadPoll：内部只存在核心线程，在构造FixedThreadPoll时可以指定核心线程数，阻塞队列使用的是无界队列LinkedBlockingQueue。
- CachedThreadPool：内部不存在核心线程，最多可以创建Integer.MAX_VALUE个线程，使用的为不存储任务的阻塞队列SynchronousQueue。
- SingleThreadExecutor：内部只存在一个核心线程，阻塞队列使用的是无界队列LinkedBlockingQueue。
- ScheduleThreadPool：最大的特点是可以延时启动任务,并且可以一直重复执行，核心线程数固定，非核心线程没有限制。用的队列是DelayedQueue。
强引用、软引用、弱引用、虚引用
强引用：
Object obj = new Object();
常规的创建一个对象，只要对象引用存在就不会被回收。
软引用：
Object obj = new Object();
SoftRefrence<Object> sf = new SoftRefrence();
Object obj = sf.get();
内存溢出之前会进行回收,可通过get()方法获取obj对象，当被标记为回收时返回null
弱引用：
Object obj = new Object();
WeakReference<Object> wf = new WeakReference<Object>(obj);
wf.get();//有时候会返回null
wf.isEnQueued();//返回是否被垃圾回收器标记为即将回收的垃圾
第二次垃圾回收时进行回收
虚引用：
Object obj = new Object();
PhantomRefrence<Object> pr = new PhantomRefrence(obj);
pr.get();//永远返回null
在每次垃圾回收时都会进行回收，一般用于检测对象是否已经从内存中删除
泛型
泛型即"参数化类型"，只代表类型不能代表对象，Java中类、接口、方法中均可存在泛型，分别对应泛型类、泛型接口、泛型方法。泛型在面向对象编程和设计模式中应用非常广泛。
注解
注解是Java1.5之后推出的新内容，作用大概有两点：
- 可以对程序作出解释(这一点跟注释没啥区别)
- 能被其他程序读取，所以可以把配置信息写到注解上，使整体逻辑变得更加清晰。
Java中注解大概分三种：
- 内置注解
@Override：代表覆盖父类方法
@Deprecated：代表已经废弃的方法、属性、类，不建议再使用
@SuppressWarnings：用来抑制编译时的警告信息 - 元注解
@Target：用与描述注解的使用范围，通过设置value值来实现
@Retention：表示在什么级别保存该注解信息，也就是注解的生命周期
@Documented：在生成javadoc的时候将该Annotation也进行写入
@Inherited
一般前两个较为常用 - 自定义注解
开发者可以结合内置注解和元注解自行定义一个注解，使用大概分三步：定
义注解、使用注解、解析注解，解析注解通常用反射来实现。
JVM内存结构与类加载
Java反射机制
在运行时，可以通过反射获取到一个类的所有信息包括类名、方法名、属性名称、注解等等，也可以操作一个对象的任意属性和方法。
反射的优点：可以动态获取类信息和操作对象，也使Java具备了一定的动态性。
反射的缺点：影响性能、暴露内容存在安全隐患。
使用方法：
获取Class对象
//path为类路径
Class<User> userClass = (Class<User>) Class.forName(path);
通过Class对象获取类对象
//方式1通过反射API调用构造方法
User user1 = userClass.newInstance();
//方式2，首先获取有参构造器
Constructor<User> constructor = userClass.getDeclaredConstructor(String.class,int.class);
User user2 = constructor.newInstance("ls",25); //通过构造器获取对象
通过反射API操作方法
User user3 = userClass.newInstance();
//动态获取方法
Method name = userClass.getDeclaredMethod("setName",String.class);
Method age = userClass.getDeclaredMethod("setAge",int.class);
name.invoke(user3,"ww");//调用user3的setName方法
age.invoke(user3,38);//调用user3的setAge方法
通过反射API操作属性
//通过反射操作属性,
User user4 = userClass.newInstance();
Field fName = userClass.getDeclaredField("name");
fName.setAccessible(true);//允许操作私有属性
Field fAge = userClass.getDeclaredField("age");
fAge.setAccessible(true);
fName.set(user4,"ml");//设置user4对象的name属性
fAge.set(user4,88);//设置user4对象的age属性
常见的设计模式
Android
什么是Context
Context是一个抽象类，Activity、Service、Application都是Context的子类。从Android系统的角度来讲它是一种场景，用来描述整个应用程序环境信息，即上下文。另外Activity的启动Service的绑定/解绑都是由Context实现。
JVM和Dalvik的区别
Activity生命周期
activity.PNG
- onCreate()：Activity正在被创建，是Activity生命周期的第一个方法，一般用于完成一些初始化信息。
- onStart()：表示启动一个Activity，使Activity处于可见状态(但此时界面没有焦点，还无法与用户进行交互)，一般动画操作可放在该方法中进行。
- onResume()：执行完这个方法Activity就会显示在界面上。
- onPause()：处于暂停阶段，与onResume()对应。一般Activity跳转时会触发该方法，从另一Activity退回当前Activity会执行onResume()。
- onStop()：处于停止状态，Activity不可见但还存在，与onStart()对应。一般点击home键返回桌面时会调用，从桌面回来时会滴哦用onStop()。
- onDestroy()：Activity已经消亡，我们可以在此方法中做资源回收，它与>* onCreate()方法对应。
- onReStart()：第一次启动Activity时不会调用，当Activity启动后执行了onStop()再进入Activity界面时会执行该方法。
Activity正确的跳转方式，通过这种方式可以提高Activity启动速度
A跳转到B：AonPause-BonCreate-BonStart-BonResume-AonStop
B退回至A：BonPause-AonReStart-AonStart-AonResume-BonStop-BonDestroy
Activity四种启动方式
- Standard：为默认模式，每创建一个Activity都会进行压栈操作，完全遵循栈数据结构的先进后出。
- SingleTop：跟Standard基本类似，唯一区别是如果需要启动的Activity已经位于栈顶就不再进行压栈操作。
- SingleTask：如果栈中已经存在需要启动的Activity，就直接使用，保证Activity只在当前任务栈中唯一，并且将上面的Activity全部清理出栈。
- SingleInstance：与SingleTask不通SingleInstance在全局中唯一，并且每开启一个新的Activity都会开启一个任务栈，也就是说每个Activity对应一个任务栈，如果需要启动的Activity栈已经存在就不再重新创建而是将创建过的Activity唤醒。
启动模式可以在清单文件中指定。
Fragment生命周期
捕获.PNG
onStart()\onResume()\onPause()\onStop()跟Activity保持一致。
- onAttach()：在Fragment和Activity绑定之后会被调用，该方法执行之后就不能再通过setArguments()进行传值。
- onCreate()：用来创建Fragment，此时Activity中的onCreate()还没有的到回调，所以不要在此方法内获取Activity一些资源。
- onCreateView()：与视图进行绑定。
- onActivityCreated()：此时Activity的onCreate方法已经执行完毕，可以获取Activity中资源。
- onDestroyView()：将Fragment与视图(UI布局)进行分离。
- onDestroy()：销毁Fragment，但此时还未与Activity解除绑定，所以在此阶段仍然可以从Activity中获取Fragment引用。
- onDetach()：与对应的Activity解绑，并释放所有资源。
Fragment与Activity、Fragment之间通信
- Activity向Fragment传值：通过setArguments、直接获取到Fragment引用。
- Fragment向Activity传值：写一个回调接口让Activity实现，再将接口引用传递给Fragment。
- Fragment向Fragment传值：通过Activity为中介使两个Fragment通讯
另外也可以使用一些非常规方法比如广播、EventBus等等。
Service启动/关闭方式
启动：
通过startService()；
通过bindService()；
区别是bindService可以实现绑定者与Service通讯并跟随绑定着生命周期。通过startService启动只能通过stopService关闭服务，否则在正常情况下会一直运行。
关闭：
通过stopService()；
通过unBindService()；
Service生命周期
service.PNG
startService：
- onCreate()：创建一个Service，如果服务已存在不在再次执行。
- onStartCommand()：多次启动Service会多次调用。
- onDestroy()：销毁服务。
bindService：
- onCreate()：创建一个Service，如果服务已存在不在再次执行。
- onBind()：绑定Service时调用
- onUnBind()：解绑Service调用
- onDestroy()：销毁服务。
- onRebind()：当使用startService启动Service同时调用bindService启动Service，且 onUnbind 返回值为 true 时，下次再次调用 bindService 将触发该方法。
IntentService
继承自Servicec，开启一个工作线程执行任务，所以如果Service中执行的为耗时任务可以使用IntentService。
广播以及注册方式
广播是一个全局的监听器，分为两个角色：广播发送者、广播接收者
自定义广播中可以在onReceive中接收到广播发送者的消息。
注册方式有两种分别是静态注册和动态注册。
静态注册：
在清单文件中注册，
动态注册：
在代码中调用Context.registerReceiver()
动态广播最好在Activity 的 onResume()注册、onPause()注销。因为对于动态广播，有注册就必然得有注销，否则会导致内存泄露。重复注册、重复注销也不允许
区别：
静态注册为常驻型，比较耗费内存、电量，但是不受其他生命周期影响。可在需要长时间监听时使用。
动态注册为非常驻型，比较灵活可跟随组件生命周期，可在需要特定时刻监听广播时使用。
消息处理机制
- Handler：将Message发送到消息队列中，处理Message消息。调用发送消息方法时会首先获取到当前发送消息的线程，通过ThreadLocal获取到当前线程的Looper对象(如果获取的Looper对象为null则会抛出异常)，随后通过Looper获取到消息队列MessageQueue将Message加入到消息队列。Handler发送Message时会将Message的target赋值为当前Handler对象。
- Looper：主要作用是维护MessageQueue并与Handler进行衔接。每个线程中只允许有一个Looper，在Android主线程已经创建了一个Looper，所以跟主线程通信不需要我们自己创建Looper。Looper创建后需要调用其loop()方法，这个方法是一个死循环，会无限的从当前线程中消息队列中取Message对象，如果获取到消息就通过Message的target(当前Handler对象)间接调用handleMessage()方法。
- MessageQueue：是一个队列，用来存储Message消息对象。它是在Looper内部创建的，所以MessageQueue也是线程独立的。
Handler机制实现线程间通讯的核心就是ThreadLocal，通过set()方法将Looper设置到当前线程，通过get()方法获取到当前线程的Looper对象，所以Handler在哪个线程中创建最终就会与哪个线程通讯。
AsyncTask原理
源码分析
AysncTask内部通过Thread+Handler实现了耗时任务执行与线程间通信，耗时任务通过Callable和FutureTask进行封装，所以也具备了取消任务功能。内部维护了两个线程池，一个线程池内部存在一个双向队列用来管理任务，另一个线程池用来执行任务。
注意点：
- 同一个AysncTask对象只能开启一次，否则会抛出异常
- 内部两个线程池均被static所修饰，所以线程池被所有的AysncTask对象共用
- 启动多个异步任务会被逐个执行也就是串行，具体可见源码分析。
View绘制流程
View的绘制流程从ViewRootImp的performTraversals()方法开始，大致流程可分为measure、layout、draw，performTraversals()执行后会遍历整个View树逐个逐个进行以上三种操作
- measure()：为宽高测量，如果是ViewGroup不仅要测量自己的宽高还要测量子View的宽高，子View中onMeasure()中的两个宽高参数就是其父View经过测量传入的，所以子View的宽高一般会依赖于父View。
- layout()：为位置确定，如果是ViewGroup不仅要通过layout()确定在父View中的位置，还要重写onLayout()方法确定子View的位置。非ViewGroup的View不需要重写onLayout()方法，因为它没有子View。另外layout()方法属于View类，所以具体怎么排放不需要开发者关心。
- draw()：为图像绘制，最终会调用View的onDraw()方法，可在onDraw()方法中通过Canvas对图像进行渲染，每个View都具备这个方法。
Paint、Canvas、Path、PathMeasure、Matrix
- Paint：是一种画笔，可以设置图像的颜色、线段宽度、阴影、文字大小等等。
- Canvas：可理解为画布，需要与Paint配合使用，可以绘制出一些形状如圆、线段、矩形、弧形等等。并可通过save()和restore()对当前画布进行保存和重置。
- Path：路径，可以定义不规则的形状，最后可通过Canvas将不规则形状绘制出来。
- PathMeasure：用来测量Path，能截取Path中的某一段，通常可以实现一些炫酷的动画效果，比如不规则形状动态绘制。
- Matrix：为矩阵的意思，可以用来对画布做几何变换如：旋转、平移、缩放、错切。也可以结合Camera实现3D效果。
View几种滑动方式以及区别
- scrollTo：这个方法属于View，调用这个方法可以实现View的滑动，但滑动的是View的内容而不是View本身，ViewGroup滑动的是所有子View，非ViewGroup的View滑动的是画布，最终会改变scrollX/scrillY的值。
- translationX：通过动画的方式改变View的位置，这种方式会产生一种镜像也就是说View相对于ViewGroup的位置是不变的，只是将View的渲染效果进行了移动，最终会改变translationX/translationY的值。
- LayoutParams：通过这种方式可以改变View在ViewGroup中的位置，是会直接改变其在坐标系中X/Y值的。
Activity、Window、View区别
activity.PNG
- Activity：是Android中与用户交互的界面，通过生命周期可管控业务逻辑。
- Window：可以形容成Activity的下属，帮Activity管理View。PhoneWindow是Window的唯一实现类，内部存在一个DecorView类，DecorView是一个FramLayout内部存在唯一子View LinearLayout，LinearLayout又可分为三部分：状态栏、标题栏、ContenView。
- View：是Android中的视图，一个界面有多个View拼接而成。
事件分发机制
屏幕上的触发事件会在Activity->ViewGroup->View之间传递，通过以下三个方法可控制时间的传递与消费：
- dispatchTouchEvent(MotionEvent ev)：是事件分发的起点，如果返回值为父类方法就向下分发，如果为true消费事件即终止事件，如果为false将事件返回给父View的onTouchEvent()方法。
- onInterceptTouchEvent(MotionEvent ev)：这个方法是ViewGroup独有的，Activity和View内部没有这个方法，是用来控制事件拦截的，如果返回值为父类方法或false正常将事件分发给子View，如果为true拦截事件交由自己的onTouchEvent()方法处理。在这个方法里做些处理能解决滑动冲突。
- onTouchEvent(MotionEvent ev)：真正的事件一般会在这个方法里面处理，如果返回值父类方法或者false将时间传递给父View的onTouchEvent()方法，如果为true则消费事件。
屏幕适配
动画
Android中动画分为视图动画和属性动画
视图动画：
- 帧动画：跟动画片一样，将一张图片视为一帧，然后播放形成动画效果
- 补间动画：补间动画可以设置View的透明度、平移、旋转、缩放，补间动画有一个特点，当对一个View进行平移时只是对View的图像进行平移View实际位置是不变的。
属性动画：
- ValueAnimator：ValueAnimator并不是直接实现View动画效果，它只是提供一个算法，在一定的时间内让一个值平滑的过度到另一个值，如果想实现View动画效果还需要开发者在回调方法内对View属性进行设置。ValueAnimator的作用和Scroller类似，只是提供一套算法。另外ValueAnimator可以针对任何对象并不仅局限于View。
- ObjectAnimator：ObjectAnimator可以对一个对象的属性进行平滑的变换，这个过程不需要开发者自己去实现，只需要给出对象属性名称并在相应类中提供该属性的set()方法。这种方法也是针对于Object。
UDP、TCP
HTTP、HTTPS
Volley、OKHttp原理以及各自优缺点
Volley源码分析
OKHttp源码分析
Volley：
- 原理：Volley基于HttpUrlConnection和HttpClient，发起一个请求后会将该请求加入到RequestQueue中，RequestQueue内部维护了一个网络请求队列和一个缓存队列，请求会首先加入到缓存队列。RequestQueue也会开启多个网络请求线程和缓存线程，这些线程会一直从请求队列中取出请求，网络请求线程取出请求后进行网络请求，缓存线程取出请求后会尝试从缓存中取，如果缓存中不存在就将请求加入到网络请求队列从网络获取，获取到response后通过Handler响应给UI线程。
- 优点：通过ByteArrayPool缓存byte[]数组，从而提高IO流读写效率，适合数据量小频繁的网络请求。内部可自动解析Json、Bitmap。
- 缺点：每次上传数据或者下载数据都会将完整的数据读取到内存中，，所以下载大文件很可能触发OOM。
OKHttp：
- 原理：内部存在5个拦截器，每个拦截器各司其职基于责任链模式运行，发起一个请求后会启动第一个拦截器用于初始化信息寄存在Chain 对象中然后传析GZIP，第三个拦截器用于处理HTTP缓存，如果能从缓存中获取直接返回，第四个拦截器初始化connection和stream，第五个拦截器实现网络请求。递给下一个拦截器，第二个拦截器用于补全header、响应阶段保存Cookie、解
- 优点：支持GZIP、通过连接池对连接进行缓存、允许同一主机名共享Socket连接、可自定义拦截器。
- 缺点：没啥缺点，已经成为Android官方网络请求框架
进程间通信
- 通过Content Provider使多个应用共享数据。
- 通过Socket，即网络通讯。
- 通过AIDL接口，原理为Binder机制。
内存优化
Android中容易产生内存泄漏的点：
- 使用单例模式：在单例中尽量不要传入Activity引用。
- 使用内部类：加上静态跟弱引用
- 资源未关闭：IO流使用完毕后要关闭
- 设置监听：再观察者模式中，如果Activity中设置有监听应在onPause中将监听注销。
- 使用Bitmap：Bitmap使用完毕后应该进行回收操作。
数据结构与算法
数组
数组数据结构属于线性数据结构，内部由数组实现，在Java中对应的是ArrayList。
手写ArrayList：
public class ZsArrayList<E> implements Iterable<E> {
private static final int DEFAULT_LENGTH = 10;//默认长度
private int size;//当前元素个数
private Object[] arr = new Object[DEFAULT_LENGTH];//当前存储元素的数组
public ZsArrayList(){
size = 0;
setLength(DEFAULT_LENGTH);
}
//扩容数组
private void setLength(int targetLength){
if (targetLength<=arr.length){
return;
}
Object[] oldArr = arr;
Object[] arr = new Object[targetLength];
for (int i =0;i<size;i++){
arr[i] = oldArr[i];
}
}
//在末尾处添加元素
public void add(E e){
add(e,size);
}
//将元素添加到index处
public void add(E e,int index){
if(index>size||index<0){
throw new IndexOutOfBoundsException();
}
//扩容
if(arr.length==size){
setLength(size+DEFAULT_LENGTH);
}
for (int i = size;i>index;i--){
arr[i] = arr[i-1];
}
arr[index] = e;
size++;
}
//移除index处的元素
public E remove(int index){
checkIndex(index);
E oldE = (E) arr[index];
for (int i=index;i<size-1;i++){
arr[i] = arr[i+1];
}
size--;
return oldE;
}
//替换index处元素
public E set(E e,int index){
checkIndex(index);
E oldE = (E) arr[index];
arr[index] = e;
return oldE;
}
//获取index处元素
public E get(int index){
checkIndex(index);
return (E) arr[index];
}
//重置
public void clear(){
size = 0;
setLength(DEFAULT_LENGTH);
}
//校验角标是否越界
private void checkIndex(int index){
if(index>=size||index<0){
throw new IndexOutOfBoundsException();
}
}
@Override
public Iterator<E> iterator() {
return new ZsArrayIterator();
}
class ZsArrayIterator implements Iterator<E>{
int currentIndex = 0;
@Override
public boolean hasNext() {
return currentIndex<size;
}
@Override
public E next() {
if (!hasNext()){
throw new IndexOutOfBoundsException();
}
return (E) arr[currentIndex++];
}
@Override
public void remove() {
ZsArrayList.this.remove(currentIndex--);
}
}
}
链表
链表数据结构一般分为三种：单向链表、双向链表、双向循环链表
手写LinkedList(单向链表)：
public class ZsLinkedList01<E> implements Iterable<E> {
private int size;//元素个数
private Node<E> head;//头结点
public ZsLinkedList01(){
size=0;
head = null;
}
//将元素添加到尾部
public void add(E e){
add(e,size);
}
//将元素添加到index处
public void add(E e,int index){
if(index<0||index>size){
throw new IndexOutOfBoundsException();
}
Node<E> node = new Node<>(e,null);
if(index==0){
node.next = head;
head = node;
}else if (index == size){
Node<E> end = node(size-1);
end.next = node;
}else {
Node<E> oldIndexNode = node(index);
Node<E> preNode = node(index-1);
preNode.next = node;
node.next = oldIndexNode;
}
size++;
}
//删除index处元素
public Node<E> remove(int index){
checkIndex(index);
Node<E> rtNode = node(index);
if(index==0){
Node<E> firstNode = node(0);
head = firstNode.next;
}else if(index==size-1){
Node<E> lastNode = node(size-2);
lastNode.next = null;
}else {
Node<E> oldIndexNode = node(index);
Node<E> preNode = node(index-1);
preNode.next = oldIndexNode.next;
}
size--;
return rtNode;
}
//替换index处元素
public void set(E e,int index){
checkIndex(index);
node(index).data = e;
}
//获取index处元素
public E get(int index){
checkIndex(index);
return node(index).data;
}
//获取index处节点对象
private Node<E> node(int index){
checkIndex(index);
Node<E> currentNode = head;
for (int i = 1;i<=index;i++){
currentNode = currentNode.next;
}
return currentNode;
}
//清除
public void clear(){
size=0;
head = null;
}
//角标校验
private void checkIndex(int index){
if(index<0||index>=size){
throw new IndexOutOfBoundsException();
}
}
@Override
public Iterator<E> iterator() {
return new ZsLinkedIterator<>();
}
class ZsLinkedIterator<E> implements Iterator<E>{
int currentIndex = 0;//当前角标
@Override
public boolean hasNext() {
return currentIndex<size;
}
@Override
public E next() {
if(!hasNext()){
throw new IndexOutOfBoundsException();
}
return (E) get(currentIndex++);
}
@Override
public void remove() {
ZsLinkedList01.this.remove(currentIndex--);
}
}
//节点对象
class Node<E>{
public E data;//数据
public Node<E> next;//下一个节点对象
public Node(E data,Node<E> next){
this.data = data;
this.next = next;
}
}
}
栈
栈数据结构遵循先进后出，一般基于数组和链表实现
手写Stack：
public class ZsStack<E>{
private ZsArrayList<E> arr;
public ZsStack(){
arr = new ZsArrayList<>();
}
//压栈
public void put(E e){
arr.add(e);
}
//弹栈
public E pop(){
E e = arr.get(arr.size()-1);
arr.remove(arr.size()-1);
return e;
}
//查看栈顶元素
public E peek(){
return arr.get(arr.size()-1);
}
//是否为空
public boolean isEmpty(){
return arr.size()==0;
}
}
队列
队列数据结构遵循先见先出，一般也是基于数组和链表实现
手写Queue：
public class ZsQueue<E> {
private ZsArrayList<E> arr;
public ZsQueue(){
arr = new ZsArrayList<>();
}
//入队
public void add(E e){
arr.add(e);
}
//出队
public E poll(){
E e = arr.get(0);
arr.remove(0);
return e;
}
public boolean isEmpty(){
return arr.size()==0;
}
}
散列表
散列表内部由数组存储元素，通过hash算法计算出存储角标，但不同元素hash值可能相同，一般情况下通过链表解决hash冲突
手写HashMap：
public class ZsHashMap<K,V> {
private Node<K,V>[] nodes;//存储头节点的数组
private int size;//元素个数
private static int defaultCapacity = 16;//默认容量
private static float defaultLoadFactor = 0.75f;//扩展因子
public ZsHashMap(){
}
public ZsHashMap(int capacity,int loadFactor){
defaultCapacity = capacity;
defaultLoadFactor = loadFactor;
}
//添加元素
public V put(K key,V value){
if(nodes==null){
nodes = new Node[defaultCapacity];
}
int index = hash(key);
Node<K,V> node = nodes[index];
while (node!=null){
if(node.key.equals(key)){
node.value = value;
return value;
}else {
node = node.next;
}
}
//判断是否需要扩展
if(size>=defaultCapacity*defaultLoadFactor){
resize();
}
//将新添加的数据作为头结点添加到数组中
nodes[index] = new Node<>(key,value,nodes[index]);
size++;
return value;
}
//获取元素
public V get(K key){
int index = hash(key);
Node<K,V> node = nodes[index];
if(node!=null){
while (node!=null&&!node.key.equals(key)){
node = node.next;
}
if(node==null){
return null;
}else {
return node.value;
}
}
return null;
}
//扩展数组
public void resize(){
size=0;
Node<K,V>[] oldNodes = nodes;
defaultCapacity = defaultCapacity*2;
nodes = new Node[defaultCapacity];
for (int i = 0;i<oldNodes.length;i++){
//扩容后hash值会改变，所以要重新散列
Node<K,V> node = oldNodes[i];
while (node!=null){
Node<K,V> oldNode = node;
put(node.key,node.value);//散列
node = node.next;//角标往后移
oldNode.next = null;//将当前散列的节点next置为null
}
}
}
//hash算法
public int hash(K key){
int code = key.hashCode();
return code%(defaultCapacity-1);
}
//节点对象
public class Node<K,V>{
K key;
V value;
Node<K,V> next;
public Node(K key,V value,Node<K,V> next){
this.key = key;
this.value = value;
this.next = next;
}
}
}
HashMap多线程问题
HashMap在多线程存在安全问题，多线程中应该使用ConcurrentHashMap
排序算法
链表反转
单链表反转
//单链表反转
public void reverse(){
Node<E> prev = null;
Node<E> currentNode = head;
while (currentNode !=null){
Node<E> next = currentNode.next;
currentNode.next = prev;
prev = currentNode;
currentNode = next;
}
head = prev;
}
网友评论