plokmju88

plokmju88 查看完整档案

北京编辑  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑

大家好,我是承香墨影。
Segmentfault发布的文章均来自公众帐号『承香墨影(cxmyDev)』,在每周末会统一更新一次公众号的文章。
想第一时间看到新鲜的文章,可以关注公众帐号。谢谢。

个人动态

plokmju88 发布了文章 · 3月23日

聊聊OkHttp实现WebSocket细节,包括鉴权和长连接保活及其原理!

一、序

OkHttp 应该算是 Android 中使用最广泛的网络库了,我们通常会利用它来实现 HTTP 请求,但是实际上它还可以支持 WebSocket,并且使用起来还非常的便捷。

那本文就来聊聊,利用 OkHttp 实现 WebSocket 的一些细节,包括对 WebSocket 的介绍,以及在传输前如何做到鉴权、长连接保活及其原理。

二、WebSocket 简介

2.1 为什么使用 WebSocket?

我们做客户端开发时,接触最多的应用层网络协议,就是 HTTP 协议,而今天介绍的 WebSocket,下层和 HTTP 一样也是基于 TCP 协议,这是一种轻量级网络通信协议,也属于应用层协议。

WebSocket 与 HTTP/2 一样,其实都是为了解决 HTTP/1.1 的一些缺陷而诞生的,而 WebSocket 针对的就是「请求-应答」这种"半双工"的模式的通信缺陷。

「请求-应答」是"半双工"的通信模式,数据的传输必须经过一次请求应答,这个完整的通信过程,通信的同一时刻数据只能在一个方向上传递。它最大的问题在于,HTTP 是一种被动的通信模式,服务端必须等待客户端请求才可以返回数据,无法主动向客户端发送数据。

这也导致在 WebSocket 出现之前,一些对实时性有要求的服务,通常是基于轮询(Polling)这种简单的模式来实现。轮询就是由客户端定时发起请求,如果服务端有需要传递的数据,可以借助这个请求去响应数据。

轮询的缺点也非常明显,大量空闲的时间,其实是在反复发送无效的请求,这显然是一种资源的损耗。

虽然在之后的 HTTP/2、HTTP/3 中,针对这种半双工的缺陷新增了 Stream、Server Push 等特性,但是「请求-应答」依然是 HTTP 协议主要的通信方式。

WebSocket 协议是由 HTML5 规范定义的,原本是为了浏览器而设计的,可以避免同源的限制,浏览器可以与任意服务端通信,现代浏览器基本上都已经支持 WebSocket。

虽然 WebSocket 原本是被定义在 HTML5 中,但它也适用于移动端,尽管移动端也可以直接通过 Socket 与服务端通信,但借助 WebSocket,可以利用 80(HTTP) 或 443(HTTPS)端口通信,有效的避免一些防火墙的拦截。

WebSocket 是真正意义上的全双工模式,也就是我们俗称的「长连接」。当完成握手连接后,客户端和服务端均可以主动的发起请求,回复响应,并且两边的传输都是相互独立的。

2.2 WebSocket 的特点

WebSocket 的数据传输,是基于 TCP 协议,但是在传输之前,还有一个握手的过程,双方确认过眼神,才能够正式的传输数据。

WebSocket 的握手过程,符合其 "Web" 的特性,是利用 HTTP 本身的 "协议升级" 来实现。

在建立连接前,客户端还需要知道服务端的地址,WebSocket 并没有另辟蹊径,而是沿用了 HTTP 的 URL 格式,但协议标识符变成了 "ws" 或者 "wss",分别表示明文和加密的 WebSocket 协议,这一点和 HTTP 与 HTTPS 的关系类似。

以下是一些 WebSocket 的 URL 例子:

ws://cxmydev.com/some/path
ws://cxmydev.com:8080/some/path
wss://cxmydev.com:443?uid=xxx

而在连接建立后,WebSocket 采用二进制帧的形式传输数据,其中常用的包括用于数据传输的数据帧 MESSAGE 以及 3 个控制帧:

  • PING:主动保活的 PING 帧;
  • PONG:收到 PING 帧后回复;
  • CLOSE:主动关闭 WebSocket 连接;

更多 WebSocket 的协议细节,可以参考《WebSocket Protocol 规范》,具体细节,有机会为什么再开单篇文章讲解。

了解这些基本知识,我们基本上就可以把 WebSocket 使用起来,并且不会掉到坑里。

我们再小结一下 WebSocket 的特性:

  1. WebSocket 建立在 TCP 协议之上,对服务器端友好;
  2. 默认端口采用 80 或 443,握手阶段采用 HTTP 协议,不容易被防火墙屏蔽,能够通过各种 HTTP 代理服务器;
  3. 传输数据相比 HTTP 更轻量,少了 HTTP Header,性能开销更小,通信更高效;
  4. 通过 MESSAGE 帧发送数据,可以发送文本或者二进制数据,如果数据过大,会被分为多个 MESSAGE 帧发送;
  5. WebSocket 沿用 HTTP 的 URL,协议标识符是 "ws" 或 "wss"。

那接下来我们就看看如何利用 OkHttp 使用 WebSocket。

三、WebSocket之OkHttp

3.1 建立 WebSocket 连接

借助 OkHttp 可以很轻易的实现 WebSocket,它的 OkHttpClient 中,提供了 newWebSocket() 方法,可以直接建立一个 WebSocket 连接并完成通信。

fun connectionWebSockt(hostName:String,port:Int){
  val httpClient = OkHttpClient.Builder()
      .pingInterval(40, TimeUnit.SECONDS) // 设置 PING 帧发送间隔
      .build()
  val webSocketUrl = "ws://${hostName}:${port}"
  val request = Request.Builder()
      .url(webSocketUrl)
      .build()
  httpClient.newWebSocket(request, object:WebSocketListener(){
    // ...
  })
}

我想熟悉 OkHttp 的朋友,对上面这端代码不会有疑问,只是 URL 换成了 "ws" 协议标识符。另外,还需要配置 pingInterval(),这个细节后文会讲解。

调用 newWebSocket() 后,就会开始 WebSocket 连接,但是核心操作都在 WebSocketListener 这个抽象类中。

3.2 使用 WebSocketListener

WebSocketListener 是一个抽象类,其中定义了比较多的方法,借助这些方法回调,就可以完成对 WebSocket 的所有操作。

var mWebSocket : WebSocket? = null
fun connectionWebSockt(hostName:String,port:Int){
  // ...
  httpClient.newWebSocket(request, object:WebSocketListener(){
    override fun onOpen(webSocket: WebSocket, response: Response) {
      super.onOpen(webSocket, response)
      // WebSocket 连接建立
      mWebSocket = webSocket
    }

    override fun onMessage(webSocket: WebSocket, text: String) {
      super.onMessage(webSocket, text)
      // 收到服务端发送来的 String 类型消息
    }

    override fun onClosing(webSocket: WebSocket, code: Int, reason: String) {
      super.onClosing(webSocket, code, reason)
      // 收到服务端发来的 CLOSE 帧消息,准备关闭连接
    }

    override fun onClosed(webSocket: WebSocket, code: Int, reason: String) {
      super.onClosed(webSocket, code, reason)
      // WebSocket 连接关闭
    }

    override fun onFailure(webSocket: WebSocket, t: Throwable, response: Response?) {
      super.onFailure(webSocket, t, response)
      // 出错了
    }
  })
}

WebSocketListener 的所有方法回调中,都包含了 WebSocket 类型的对象,它就是当前建立的 WebSocket 连接实体,通过它就可以向服务端发送 WebSocket 消息。

如果需要在其他时机发送消息,可以在回调 onOpen() 这个建立连接完成的时机,保存 webSocket 对象,以备后续使用。

OkHttp 中的 WebSocket 本身是一个接口,它的实现类是 RealWebSocket,它定义了一些发送消息和关闭连接的方法:

  • send(text):发送 String 类型的消息;
  • send(bytes):发送二进制类型的消息;
  • close(code, reason):主动关闭 WebSocket 连接;

利用这些回调和 WebSocket 提供的方法,我们就可以完成 WebSocket 通信了。

3.3 Mock WebSocket

有时候为了方便我们测试,OkHttp 还提供了扩展的 MockWebSocket 服务,来模拟服务端。

MockWebSocket 需要添加额外的 Gradle 引用,最好和 OkHttp 版本保持一致:

api 'com.squareup.okhttp3:okhttp:3.9.1'
api 'com.squareup.okhttp3:mockwebserver:3.9.1'

MockWebServer 的使用也非常简单,只需要利用 MockWebSocket 类即可。

var mMockWebSocket: MockWebServer? = null
fun mockWebSocket() {
  if (mMockWebSocket != null) {
    return
  }
  mMockWebSocket = MockWebServer()
  mMockWebSocket?.enqueue(MockResponse().withWebSocketUpgrade(object : WebSocketListener() {

    override fun onOpen(webSocket: WebSocket, response: Response) {
      super.onOpen(webSocket, response)
      // 有客户端连接时回调
    }

    override fun onMessage(webSocket: WebSocket, text: String) {
      super.onMessage(webSocket, text)
      // 收到新消息时回调
    }

    override fun onClosing(webSocket: WebSocket, code: Int, reason: String) {
      super.onClosing(webSocket, code, reason)
      // 客户端主动关闭时回调
    }

    override fun onClosed(webSocket: WebSocket, code: Int, reason: String) {
      super.onClosed(webSocket, code, reason)
      // WebSocket 连接关闭
    }

    override fun onFailure(webSocket: WebSocket, t: Throwable, response: Response?) {
      super.onFailure(webSocket, t, response)
      // 出错了
    }
  }))
}

Mock WebSocket 服务端,依然需要用到我们前面讲到的 WebSocketListener,这个就比较熟悉,不再赘述了。

之后就可以通过 mMockWebSocket 获取到这个 Mock 的服务的 IP 和端口。

val hostName = mMockWebSocket?.getHostName()
val port = mMockWebSocket?.getPort()
val url = "ws:${hostName}:${port}"

需要注意的是,这两个方法需要在子线程中调用,否者会收到一个异常。

虽然有时候在服务端完善的情况下,我们并不需要使用 Mock 的手段,但是在学习阶段,依然推荐大家在本地 Mock 一个服务端,打一些日志,观察一个完整的 WebSocket 连接和发送消息的过程。

3.4 WebSocket 如何鉴权

接下来我们聊聊 WebSocket 连接的鉴权问题。

所谓鉴权,其实就是为了安全考虑,避免服务端启动 WebSocket 的连接服务后,任谁都可以连接,这肯定会引发一些安全问题。其次,服务端还需要将 WebSocket 的连接实体与一个真是的用户对应起来,否者业务无法保证了。

那么问题就回到了,WebSocket 通信的完整过程中,如何以及何时将一些业务数据传递给服务端?当然在 WebSocket 连接建立之后,立即给服务端发送一些鉴权的数据,必然是可以做到业务实现的,但是这样明显是不够优雅的。

前文提到,WebSocket 在握手阶段,使用的是 HTTP 的 "协议升级",它本质上还是 HTTP 的报文头发送一些特殊的头数据,来完成协议升级。

例如在 RealWebSocket 中,就有构造 Header 的过程,如 Upgrade、Connection 等等。

public void connect(OkHttpClient client) {
  // ...
  final Request request = originalRequest.newBuilder()
    .header("Upgrade", "websocket")
    .header("Connection", "Upgrade")
    .header("Sec-WebSocket-Key", key)
    .header("Sec-WebSocket-Version", "13")
    .build();
  //....
}

那么实际我们在 WebSocket 阶段,也可以通过 Header 传输一些鉴权的数据,例如 uid、token 之类,具体方法就是在构造 Request 的时候,为其增加 Header,这里就不举例说明了。

另外 WebSocket 的 URL 也是可以携带参数的。

wss://cxmydev.com:443?uid=xxx&token=xxx

3.5 WebSocket 保活

WebSocket 建立的连接就是我们所谓的长连接,每个连接对于服务器而言,都是资源。但服务器倾向于在一个连接长时间没有消息往来的时候,将其关闭。而 WebSocket 的保活,实际上就是定时向服务端发送一个空消息,来保证连接不会被服务端主动断开。

那么我们自己写个定时器,固定间隔向服务端 mWebSocket.send() 一个消息,就可以达到保活的目的,但这样发送的其实是 MESSAGE 帧数据,如果使用 WebSocket 还有更优雅的方式。

前文我们提到,WebSocket 采用二进制帧的形式传输数据,其中就包括了用于保活的 PING 帧,而 OkHttp 只需要简单的配置,就可以自动的间隔发送 PING 帧和数据。

我们只需要在构造 OkHttpClient 的时候,通过 pingInterval() 设置 PING 帧发送的时间间隔,它的默认值为 0,所以不设置不发送。

val httpClient = OkHttpClient.Builder()
      .pingInterval(40, TimeUnit.SECONDS) // 设置 PING 帧发送间隔
      .build()

这里设置的时长,需要和服务端商议,通常建议最好设置一个小于 60s 的值。

具体的逻辑在 RealWebSocket 类中。

public void initReaderAndWriter(String name, Streams streams) throws IOException {
  synchronized (this) {
    // ...
    if (pingIntervalMillis != 0) {
      executor.scheduleAtFixedRate(
        new PingRunnable(), pingIntervalMillis, pingIntervalMillis, MILLISECONDS);
    }
    // ...
  }
  // ...
}

PingRunnabel 最终会去间隔调用 writePingFrame() 用以向 WebSocketWriter 中写入 PING 帧,来达到服务端长连接保活的效果。

四、小结

到这里本文就介绍清楚 WebSocket 以及如何使用 OkHttp 实现 WebSocket 支持。

这里还是简单小结一下:

  1. WebSocket 是一个全双工的长连接应用层协议,可以通过它实现服务端到客户端主动的推送通信。
  2. OkHttp 中使用 WebSocket 的关键在于 newWebSocket() 方法以及 WebSocketListener 这个抽象类,最终连接建立完毕后,可以通过 WebSocket 对象向对端发送消息;
  3. WebSocket 鉴权,可以利用握手阶段的 HTTP 请求中,添加 Header 或者 URL 参数来实现;
  4. WebSocket 的保活,需要定时发送 PING 帧,发送的时间间隔,在 OkHttp 中可以通过 pingInterval() 方法设置;

额外提一句,OkHttp 在 v3.4.1 中添加的 WebSocket 的支持,之前的版本需要 okhttp-ws 扩展库来支持,但是那毕竟已经是 2016 年的事了,我想现在应该没有人在用那么老版本的 OkHttp 了。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!如果本文各项数据好,之后会再分享一篇 OkHttp 中针对 WebSocket 的实现以及 WebSocket 协议的讲解。

参考:


热文推荐:

公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 0 收藏 0 评论 0

plokmju88 发布了文章 · 2月20日

面试官:“看你简历上写熟悉 Handler 机制,那聊聊 IdleHandler 吧?”

一. 序

Handler 机制算是 Android 基本功,面试常客。但现在面试,多数已经不会直接让你讲讲 Handler 的机制,Looper 是如何循环的,MessageQueue 是如何管理 Message 等,而是基于场景去提问,看看你对 Handler 机制的掌握是否扎实。

本文就来聊聊 Handler 中的 IdleHandler,这个我们比较少用的功能。它能干什么?怎么使用?有什么合适的使用场景?哪些不是合适的使用场景?在 Android Framework 中有哪些地方用到了它?

二. IdleHandler

2.1 简单说说 Handler 机制

在说 IdleHandler 之前,先简单了解一下 Handler 机制。

Handler 是标准的事件驱动模型,存在一个消息队列 MessageQueue,它是一个基于消息触发时间的优先级队列,还有一个基于此消息队列的事件循环 Looper,Looper 通过循环,不断的从 MessageQueue 中取出待处理的 Message,再交由对应的事件处理器 Handler/callback 来处理。

其中 MessageQueue 被 Looper 管理,Looper 在构造时同步会创建 MessageQueue,并利用 ThreadLocal 这种 TLS,将其与当前线程绑定。而 App 的主线程在启动时,已经构造并准备好主线程的 Looper 对象,开发者只需要直接使用即可。

Handler 类中封装了大部分「Handler 机制」对外的操作接口,可以通过它的 send/post 相关的方法,向消息队列 MessageQueue 中插入一条 Message。在 Looper 循环中,又会不断的从 MessageQueue 取出下一条待处理的 Message 进行处理。

IdleHandler 使用相关的逻辑,就在 MessageQueue 取消息的 next() 方法中。

2.2 IdleHandler 是什么?怎么用?

IdleHandler 说白了,就是 Handler 机制提供的一种,可以在 Looper 事件循环的过程中,当出现空闲的时候,允许我们执行任务的一种机制。

IdleHandler 被定义在 MessageQueue 中,它是一个接口。

// MessageQueue.java
public static interface IdleHandler {
  boolean queueIdle();
}

可以看到,定义时需要实现其 queueIdle() 方法。同时返回值为 true 表示是一个持久的 IdleHandler 会重复使用,返回 false 表示是一个一次性的 IdleHandler。

既然 IdleHandler 被定义在 MessageQueue 中,使用它也需要借助 MessageQueue。在 MessageQueue 中定义了对应的 add 和 remove 方法。

// MessageQueue.java
public void addIdleHandler(@NonNull IdleHandler handler) {
    // ...
  synchronized (this) {
    mIdleHandlers.add(handler);
  }
}
public void removeIdleHandler(@NonNull IdleHandler handler) {
  synchronized (this) {
    mIdleHandlers.remove(handler);
  }
}

可以看到 add 或 remove 其实操作的都是 mIdleHandlers,它的类型是一个 ArrayList。

既然 IdleHandler 主要是在 MessageQueue 出现空闲的时候被执行,那么何时出现空闲?

MessageQueue 是一个基于消息触发时间的优先级队列,所以队列出现空闲存在两种场景。

  1. MessageQueue 为空,没有消息;
  2. MessageQueue 中最近需要处理的消息,是一个延迟消息(when>currentTime),需要滞后执行;

这两个场景,都会尝试执行 IdleHandler。

处理 IdleHandler 的场景,就在 Message.next() 这个获取消息队列下一个待执行消息的方法中,我们跟一下具体的逻辑。

Message next() {
    // ...
  int pendingIdleHandlerCount = -1; 
  int nextPollTimeoutMillis = 0;
  for (;;) {
    nativePollOnce(ptr, nextPollTimeoutMillis);

    synchronized (this) {
      // ...
      if (msg != null) {
        if (now < msg.when) {
          // 计算休眠的时间
          nextPollTimeoutMillis = (int) Math.min(msg.when - now, Integer.MAX_VALUE);
        } else {
          // Other code
          // 找到消息处理后返回
          return msg;
        }
      } else {
        // 没有更多的消息
        nextPollTimeoutMillis = -1;
      }
      
      if (pendingIdleHandlerCount < 0
          && (mMessages == null || now < mMessages.when)) {
        pendingIdleHandlerCount = mIdleHandlers.size();
      }
      if (pendingIdleHandlerCount <= 0) {
        mBlocked = true;
        continue;
      }

      if (mPendingIdleHandlers == null) {
        mPendingIdleHandlers = new IdleHandler[Math.max(pendingIdleHandlerCount, 4)];
      }
      mPendingIdleHandlers = mIdleHandlers.toArray(mPendingIdleHandlers);
    }

    for (int i = 0; i < pendingIdleHandlerCount; i++) {
      final IdleHandler idler = mPendingIdleHandlers[i];
      mPendingIdleHandlers[i] = null; 

      boolean keep = false;
      try {
        keep = idler.queueIdle();
      } catch (Throwable t) {
        Log.wtf(TAG, "IdleHandler threw exception", t);
      }

      if (!keep) {
        synchronized (this) {
          mIdleHandlers.remove(idler);
        }
      }
    }

    pendingIdleHandlerCount = 0;
    nextPollTimeoutMillis = 0;
  }
}

我们先解释一下 next() 中关于 IdleHandler 执行的主逻辑:

  1. 准备执行 IdleHandler 时,说明当前待执行的消息为 null,或者这条消息的执行时间未到;
  2. pendingIdleHandlerCount < 0 时,根据 mIdleHandlers.size() 赋值给 pendingIdleHandlerCount,它是后期循环的基础;
  3. mIdleHandlers 中的 IdleHandler 拷贝到 mPendingIdleHandlers 数组中,这个数组是临时的,之后进入 for 循环;
  4. 循环中从数组中取出 IdleHandler,并调用其 queueIdle() 记录返回值存到 keep 中;
  5. keep 为 false 时,从 mIdleHandler 中移除当前循环的 IdleHandler,反之则保留;

可以看到 IdleHandler 机制中,最核心的就是在 next() 中,当队列空闲的时候,循环 mIdleHandler 中记录的 IdleHandler 对象,如果其 queueIdle() 返回值为 false 时,将其从 mIdleHander 中移除。

需要注意的是,对 mIdleHandler 这个 List 的所有操作,都通过 synchronized 来保证线程安全,这一点无需担心。

2.3 IdleHander 是如何保证不进入死循环的?

当队列空闲时,会循环执行一遍 mIdleHandlers 数组并执行 IdleHandler.queueIdle() 方法。而如果数组中有一些 IdleHander 的 queueIdle() 返回了 true,则会保留在 mIdleHanders 数组中,下次依然会再执行一遍。

注意现在代码逻辑还在 MessageQueue.next() 的循环中,在这个场景下 IdleHandler 机制是如何保证不会进入死循环的?

有些文章会说 IdleHandler 不会死循环,是因为下次循环调用了 nativePollOnce() 借助 epoll 机制进入休眠状态,下次有新消息入队的时候会重新唤醒,但这是不对的。

注意看前面 next() 中的代码,在方法的末尾会重置 pendingIdleHandlerCount 和 nextPollTimeoutMillis。

Message next() {
    // ...
  int pendingIdleHandlerCount = -1; 
  int nextPollTimeoutMillis = 0;
  for (;;) {
        nativePollOnce(ptr, nextPollTimeoutMillis);
    // ...
    // 循环执行 mIdleHandlers
    // ...
    pendingIdleHandlerCount = 0;
    nextPollTimeoutMillis = 0;
  }
}

nextPollTimeoutMillis 决定了下次进入 nativePollOnce() 超时的时间,它传递 0 的时候等于不会进入休眠,所以说 natievPollOnce() 进入休眠所以不会死循环是不对的。

这很好理解,毕竟 IdleHandler.queueIdle() 运行在主线程,它执行的时间是不可控的,那么 MessageQueue 中的消息情况可能会变化,所以需要再处理一遍。

实际不会死循环的关键是在于 pendingIdleHandlerCount,我们看看下面的代码。

Message next() {
    // ...
  // Step 1
  int pendingIdleHandlerCount = -1; 
  int nextPollTimeoutMillis = 0;
  for (;;) {
    nativePollOnce(ptr, nextPollTimeoutMillis);

    synchronized (this) {
      // ...
      // Step 2
      if (pendingIdleHandlerCount < 0
          && (mMessages == null || now < mMessages.when)) {
        pendingIdleHandlerCount = mIdleHandlers.size();
      }
         // Step 3
      if (pendingIdleHandlerCount <= 0) {
        mBlocked = true;
        continue;
      }
      // ...
    }
        // Step 4
    pendingIdleHandlerCount = 0;
    nextPollTimeoutMillis = 0;
  }
}

我们梳理一下:

  • Step 1,循环开始前,pendingIdleHandlerCount 的初始值为 -1;
  • Step 2,在 pendingIdleHandlerCount<0 时,才会通过 mIdleHandlers.size() 赋值。也就是说只有第一次循环才会改变 pendingIdleHandlerCount 的值;
  • Step 3,如果 pendingIdleHandlerCount<=0 时,则循环 continus;
  • Step 4,重置 pendingIdleHandlerCount 为 0;

在第二次循环时,pendingIdleHandlerCount 等于 0,在 Step 2 不会改变它的值,那么在 Step 3 中会直接 continus 继续下一次循环,此时没有机会修改 nextPollTimeoutMillis

那么 nextPollTimeoutMillis 有两种可能:-1 或者下次唤醒的等待间隔时间,在执行到 nativePollOnce() 时就会进入休眠,等待再次被唤醒。

下次唤醒时,mMessage 必然会有一个待执行的 Message,则 MessageQueue.next() 返回到 Looper.loop() 的循环中,分发处理这个 Message,之后又是一轮新的 next() 中去循环。

2.4 framework 中如何使用 IdleHander?

到这里基本上就讲清楚 IdleHandler 如何使用以及一些细节,接下来我们来看看,在系统中,有哪些地方会用到 IdleHandler 机制。

在 AS 中搜索一下 IdleHandler。

简单解释一下:

  1. ActivityThread.Idler 在 ActivityThread.handleResumeActivity() 中调用。
  2. ActivityThread.GcIdler 是在内存不足时,强行 GC;
  3. Instrumentation.ActivityGoing 在 Activity onCreate() 执行前添加;
  4. Instrumentation.Idler 调用的时机就比较多了,是键盘相关的调用;
  5. TextToSpeechService.SynthThread 是在 TTS 合成完成之后发送广播;

有兴趣可以自己追一下源码,这些都是使用的场景,具体用 IdleHander 干什么,还是要看业务。

三.一些面试问题

到这里我们就讲清楚 IdleHandler 干什么?怎么用?有什么问题?以及使用中一些原理的讲解。

下面准备一些基本的问题,供大家理解。

Q:IdleHandler 有什么用?

  1. IdleHandler 是 Handler 提供的一种在消息队列空闲时,执行任务的时机;
  2. 当 MessageQueue 当前没有立即需要处理的消息时,会执行 IdleHandler;

Q:MessageQueue 提供了 add/remove IdleHandler 的方法,是否需要成对使用?

  1. 不是必须;
  2. IdleHandler.queueIdle() 的返回值,可以移除加入 MessageQueue 的 IdleHandler;

Q:当 mIdleHanders 一直不为空时,为什么不会进入死循环?

  1. 只有在 pendingIdleHandlerCount 为 -1 时,才会尝试执行 mIdleHander;
  2. pendingIdlehanderCount 在 next() 中初始时为 -1,执行一遍后被置为 0,所以不会重复执行;

Q:是否可以将一些不重要的启动服务,搬移到 IdleHandler 中去处理?

  1. 不建议;
  2. IdleHandler 的处理时机不可控,如果 MessageQueue 一直有待处理的消息,那么 IdleHander 的执行时机会很靠后;

Q:IdleHandler 的 queueIdle() 运行在那个线程?

  1. 陷进问题,queueIdle() 运行的线程,只和当前 MessageQueue 的 Looper 所在的线程有关;
  2. 子线程一样可以构造 Looper,并添加 IdleHandler;

三. 小结时刻

到这里就把 IdleHandler 的使用和原理说清除了。

IdleHandler 是 Handler 提供的一种在消息队列空闲时,执行任务的时机。但它执行的时机依赖消息队列的情况,那么如果 MessageQueue 一直有待执行的消息时,IdleHandler 就一直得不到执行,也就是它的执行时机是不可控的,不适合执行一些对时机要求比较高的任务。

本文就到这里,对你有帮助吗?有任何问题欢迎留言。觉得有帮助别忘了转发、点好看,谢谢!


推荐阅读:

公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 0 收藏 0 评论 0

plokmju88 发布了文章 · 2月13日

TCP三次握手、四次挥手出现意外情况时,为保证稳定,是如何处理的?

一. 序

当我们聊到 TCP 协议的时候,聊的最多的就是三次握手与四次挥手。但是大部分资料和文章,写的都是正常的情况下的流程。但是你有没有想过,三次握手或者四次挥手时,如果发生异常了,是如何处理的?又是由谁来处理?

TCP 作为一个靠谱的协议,在传输数据的前后,需要在双端之间建立连接,并在双端各自维护连接的状态。TCP 并没有什么特别之处,在面对多变的网络情况,也只能通过不断的重传和各种算法来保证可靠性。

建立连接前,TCP 会通过三次握手来保证双端状态正确,然后就可以正常传输数据了。当数据传输完成,需要断开连接的时候,TCP 会通过四次握手来完成双端的断连,并回收各自的资源。

我们在学习 TCP 建连和断连时,多数都在说一个标准的流程,但是网络环境是多变的,很多时候并不像教科书那样标准,那么今天就来聊聊,TCP 三次握手和四次挥手时,如果出现异常情况,是如何处理的?由是由谁来处理?

二. TCP 三次握手

2.1 简单理解三次握手

虽然是说三次握手的异常情况,我们还是先来了解一下三次握手。

在通过 TCP 传输数据时,第一步就是要先建立一个连接。TCP 建立连接的过程,就是我们常说的三次握手。

我们经常将三次握手,描述成「请求 → 应答 → 应答之应答」。

至于 TCP 握手为什么是三次?其实就是要让双端都经历一次「请求 → 应答」的过程,来确认对方还在。网络情况是多变的,双端都需要一次自己主动发起的请求和对方回复的应答过程,来确保对方和网络是正常的。

下面这张图,是比较经典的 TCP 三次握手的消息和双端状态的变化。

我们先来解释一下这张图:

1. 在初始时,双端处于 CLOSE 状态,服务端为了提供服务,会主动监听某个端口,进入 LISTEN 状态。

2. 客户端主动发送连接的「SYN」包,之后进入 SYN-SENT 状态,服务端在收到客户端发来的「SYN」包后,回复「SYN,ACK」包,之后进入 SYN-RCVD 状态。

3. 客户端收到服务端发来的「SYN,ACK」包后,可以确认对方存在,此时回复「ACK」包,并进入 ESTABLISHED 状态。

4. 服务端收到最后一个「ACK」包后,也进入 ESTABLISHED 状态。

这是正常的 TCP 三次握手,握手完成后双端都进入 ESTABLISHED 状态,在此之后,就是正常的数据传输过程。

2.2 TCP 握手的异常情况

三次握手的正常发包和应答,以及双端的状态扭转我们已经讲了,接下来就来看看在这三次握手的过程中,出现的异常情况。

1.客户端第一个「SYN」包丢了。

如果客户端第一个「SYN」包丢了,也就是服务端根本就不知道客户端曾经发过包,那么处理流程主要在客户端。

而在 TCP 协议中,某端的一组「请求-应答」中,在一定时间范围内,只要没有收到应答的「ACK」包,无论是请求包对方没有收到,还是对方的应答包自己没有收到,均认为是丢包了,都会触发超时重传机制。

所以此时会进入重传「SYN」包。根据《TCP/IP详解卷Ⅰ:协议》中的描述,此时会尝试三次,间隔时间分别是 5.8s、24s、48s,三次时间大约是 76s 左右,而大多数伯克利系统将建立一个新连接的最长时间,限制为 75s。

也就是说三次握手第一个「SYN」包丢了,会重传,总的尝试时间是 75s。

参考:《TCP/IP 卷1 18|TCP连接的建立与终止

2.服务端收到「SYN」并回复的「SYN,ACK」包丢了。

此时服务端已经收到了数据包并回复,如果这个回复的「SYN,ACK」包丢了,站在客户端的角度,会认为是最开始的那个「SYN」丢了,那么就继续重传,就是我们前面说的「错误 1」 的流程。

而对服务端而言,如果发送的「SYN,ACK」包丢了,在超时时间内没有收到客户端发来的「ACK」包,也会触发重传,此时服务端处于 SYN_RCVD 状态,会依次等待 3s、6s、12s 后,重新发送「SYN,ACK」包。

而这个「SYN,ACK」包的重传次数,不同的操作系统下有不同的配置,例如在 Linux 下可以通过 tcp_synack_retries 进行配置,默认值为 5。如果这个重试次数内,仍未收到「ACK」应答包,那么服务端会自动关闭这个连接。

同时由于客户端在没有收到「SYN,ACK」时,也会进行重传,当客户端重传的「SYN」被收到后,服务端会立即重新发送「SYN,ACK」包。

3.客户端最后一次回复「SYN,ACK」的「ACK」包丢了。

如果最后一个「ACK」包丢了,服务端因为收不到「ACK」会走重传机制,而客户端此时进入 ESTABLISHED 状态。

多数情况下,客户端进入 ESTABLISHED 状态后,则认为连接已建立,会立即发送数据。但是服务端因为没有收到最后一个「ACK」包,依然处于 SYN-RCVD 状态。

那么这里的关键,就在于服务端在处于 SYN-RCVD 状态下,收到客户端的数据包后如何处理?

这也是比较有争议的地方,有些资料里会写到当服务端处于 SYN-RCVD 状态下,收到客户端的数据包后,会直接回复 RTS 包响应,表示服务端错误,并进入 CLOSE 状态。

但是这样的设定有些过于严格,试想一下,服务端还在通过三次握手阶段确定对方是否真实存在,此时对方的数据已经发来了,那肯定是存在的。

所以当服务端处于 SYN-RCVD 状态下时,接收到客户端真实发送来的数据包时,会认为连接已建立,并进入 ESTABLISHED 状态。

实践出真知,具体测试流程可以参考这篇文章:《TCP三次握手的第三个ack丢了会怎样

那么实际情况,为什么会这样呢?

当客户端在 ESTABLISHED 状态下,开始发送数据包时,会携带上一个「ACK」的确认序号,所以哪怕客户端响应的「ACK」包丢了,服务端在收到这个数据包时,能够通过包内 ACK 的确认序号,正常进入 ESTABLISHED 状态。

参考:《What if a TCP handshake segment is lost?

4.客户端故意不发最后一次「SYN」包。

前面一直在说正常的异常逻辑,双方都还算友善,按规矩做事,出现异常主要也是因为网络等客观问题,接下来说一个恶意的情况。

如果客户端是恶意的,在发送「SYN」包后,并收到「SYN,ACK」后就不回复了,那么服务端此时处于一种半连接的状态,虽然服务端会通过 tcp_synack_retries 配置重试的次数,不会无限等待下去,但是这也是有一个时间周期的。

如果短时间内存在大量的这种恶意连接,对服务端来说压力就会很大,这就是所谓的 SYN FLOOD 攻击

这就属于安全攻防的范畴了,今天就不讨论了,有兴趣可以自行了解。

三. TCP 四次挥手

3.1 简单理解四次挥手

说完 TCP 三次握手,继续来分析 TCP 四次挥手的异常情况。

保持行文风格,在此之前,我们还是先来简单了解一下 TCP 的四次挥手。

当数据传输完成,需要断开连接的时候,TCP 会采取四次挥手的方式,来安全的断开连接。

为什么握手需要三次,而挥手需要四次呢?

本质上来说,双端都需要经过一次「分手」的过程,来保证自己和对端的状态正确。本着友好协商的态度,你先提出的分手,也要把最大的善意給对方,不能打了对方一个措手不及。你说不玩了就不玩了,那以后谁还敢和你玩。

下面这张图,是比较经典的 TCP 四次挥手的消息和双端状态的变化。

我们解释一下这张图:

1. 初始时双端还都处于 ESTABLISHED 状态并传输数据,某端可以主动发起「FIN」包准备断开连接,在这里的场景下,是客户端发起「FIN」请求。在发出「FIN」后,客户端进入 FIN-WAIT-1 状态。

2. 服务端收到「FIN」消息后,回复「ACK」表示知道了,并从 ESTABLISHED 状态进入 CLOSED-WAIT 状态,开始做一些断开连接前的准备工作。

3. 客户端收到之前「FIN」的回复「ACK」消息后,进入 FIN-WAIT-2 状态。而当服务端做好断开前的准备工作后,也会发送一个「FIN,ACK」的消息給客户端,表示我也好了,请求断开连接,并在发送消息后,服务端进入 LAST-ACK 状态。

4. 客户端在收到「FIN,ACK」消息后,会立即回复「ACK」,表示知道了,并进入 TIME_WAIT 状态,为了稳定和安全考虑,客户端会在 TIME-WAIT 状态等待 2MSL 的时长,最终进入 CLOSED 状态。

5. 服务端收到客户端回复的「ACK」消息后,直接从 LAST-ACK 状态进入 CLOSED 状态。

正常的经过四次挥手之后,双端都进入 CLOSED 状态,在此之后,双端正式断开了连接。

3.2 TCP 挥手的异常情况

四次挥手的正常发包和应答过程,我们已经简单了解了,接下来就继续看看,四次挥手过程中,出现的异常情况。

1.断开连接的 FIN 包丢了。

我们前面一直强调过,如果一个包发出去,在一定时间内,只要没有收到对端的「ACK」回复,均认为这个包丢了,会触发超时重传机制。而不会关心到底是自己发的包丢了,还是对方的「ACK」丢了。

所以在这里,如果客户端率先发的「FIN」包丢了,或者没有收到对端的「ACK」回复,则会触发超时重传,直到触发重传的次数,直接关闭连接。

对于服务端而言,如果客户端发来的「FIN」没有收到,就没有任何感知。会在一段时间后,也关闭连接。

2.服务端第一次回复的 ACK 丢了。

此时因为客户端没有收到「ACK」应答,会尝试重传之前的「FIN」请求,服务端收到后,又会立即再重传「ACK」。

而此时服务端已经进入 CLOSED-WAIT 状态,开始做断开连接前的准备工作。当准备好之后,会回复「FIN,ACK」,注意这个消息是携带了之前「ACK」的响应序号的。

只要这个消息没丢,客户端可以凭借「FIN,ACK」包中的响应序号,直接从 FIN-WAIT-1 状态,进入 TIME-WAIT 状态,开始长达 2MSL 的等待。

3.服务端发送的 FIN,ACK 丢了。

服务端在超时后会重传,此时客户端有两种情况,要么处于 FIN-WAIT-2 状态(之前的 ACK 也丢了),会一直等待;要么处于 TIME-WAIT 状态,会等待 2MSL 时间。

也就是说,在一小段时间内客户端还在,客户端在收到服务端发来的「FIN,ACK」包后,也会回复一个「ACK」应答,并做好自己的状态切换。

4.客户端最后回复的 ACK 丢了。

客户端在回复「ACK」后,会进入 TIME-WAIT 状态,开始长达 2MSL 的等待,服务端因为没有收到「ACK」的回复,会重试一段时间,直到服务端重试超时后主动断开。

或者等待新的客户端接入后,收到服务端重试的「FIN」消息后,回复「RST」消息,在收到「RST」消息后,复位服务端的状态。

5.客户端收到 ACK 后,服务端跑路了。

客户端在收到「ACK」后,进入了 FIN-WAIT-2 状态,等待服务端发来的「FIN」包,而如果服务端跑路了,这个包永远都等不到。

在 TCP 协议中,是没有对这个状态的处理机制的。但是协议不管,系统来凑,操作系统会接管这个状态,例如在 Linux 下,就可以通过 tcp_fin_timeout 参数,来对这个状态设定一个超时时间。

需要注意的是,当超过 tcp_fin_timeout 的限制后,状态并不是切换到 TIME_WAIT,而是直接进入 CLOSED 状态。

参考:《关于FIN_WAIT2

6.客户端收到 ACK 后,客户端自己跑路了。

客户端收到「ACK」后直接跑路,服务端后续在发送的「FIN,ACK」就没有接收端,也就不会得到回复,会不断的走 TCP 的超时重试的机制,此时服务端处于 LAST-ACK 状态。

那就要分 2 种情况分析:

  1. 在超过一定时间后,服务端主动断开。
  2. 收到「RST」后,主动断开连接。

「RST」消息是一种重置消息,表示当前错误了,应该回到初始的状态。如果客户端跑路后有新的客户端接入,会在此发送「SYN」以期望建立连接,此时这个「SYN」将被忽略,并直接回复「FIN,ACK」消息,新客户端在收到「FIN」消息后是不会认的,并且会回复一个「RST」消息。

参考:《Coping with the TCP TIME-WAIT state on busy Linux servers

四. 小结时刻

本文聊了 TCP 在三次握手和四次挥手的时候,出现异常的处理逻辑。

大多数情况下,都是依赖超时重传来保证 TCP 的可靠性,但是重传的次数,状态的转换,以及有哪些状态是被系统接管,这些细节,就是本文的主题。

有任何问题欢迎留言讨论,有所帮助也别忘了转发和点收藏支持一下,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 1 收藏 1 评论 0

plokmju88 发布了文章 · 2019-12-24

图解算法:单向链表做加法运算

问:给出两个非空的链表,来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且每个结点只能存储一位数字。将这两个链表相加起来,返回一个新的链表,表示他们之和。

例如:342 + 465 = 807

两数相加这道题,处理的就是最简单的数学加法运算,只是它是建立在链表的基础之上,所以难度在于对链表的处理。

加法运算,除了每一位的加法之外,还需要考虑进位的情况。针对这道题来说,链表的每一个结点存储一位数字,并且是基于自然数字逆序存储,也就是链头到链尾保持低到高位的顺序,这样就等于,进位的方向和单链表的方向一致。

由于单链表的特性,没有前驱结点,无法回头。在这道题的场景下,就只需要一次 while 循环,从链头(低位)一直处理到链尾(高位),就可以解决。但是需要注意处理进位的情况,每一位结点在计算之后,需要按 10 取余数,进行存储,多的需要进位到下一结点参与运算,正好这也符合单链表的处理思路。

那么我们就需要几个变量,一个 carry 用来记录每一位运算后的进位,还需要一个 dummy 结点,用于记录两个链表加法运算后的链表结点。

当我们处理到最长链表最后一个结点时,还需要对 carry(进位) 进行额外的处理,如果 carry 不为 0,表示继续向高位进位,需要额外在创建一个新的结点存储进位。

到这里就讲解清晰了,直接上代码。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  // 计算结果存储的 dummy 结点
  ListNode dummy = new ListNode(0);
  ListNode p = l1, q = l2, curr = dummy;
  // 进位默认为 0
  int carry = 0;
  // 进入循环,以p和q两个链表指针都走到头为结束
  while (p != null || q != null) {
    int x = (p != null) ? p.val : 0;
    int y = (q != null) ? q.val : 0;
    // 进位参与运算
    int sum = carry + x + y;
    // 计算进位
    carry = sum / 10;
    // 构造新的结点存储计算后的位数数值
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
    if (p != null) 
      p = p.next;
    if (q != null) 
      q = q.next;
  }
  // 处理数字最高位末尾进位情况
  if (carry > 0) {
    curr.next = new ListNode(carry);
  }
  return dummy.next;
}

这里用 p 和 q 分别存储了 l1 和 l2 两个链表的结点,以此为循环依据。循环跳出的条件为两个链表都走到了末尾。

每一次循环中,处理每一位结点数数值并加上进位 carry 的值,运算后将数值取余存入新的结点,并将新的进位数存入 carry 进行存储。

最后需要注意,当两个链表都处理完成之后,还需要判断最高位是否需要进位(carry > 0)。如果需要,创建一个新的链表结点存储进位值。

这道利用链表做加法运算的题,就讲解到这里,但是它还有一些变种题。

假如链表不是逆序按位存储数字呢?如果是正序存储。

例如:

1 → 2 → 3

+3 → 2 → 1

=> 123 + 321 = ?

那么如何计算呢?

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 0 收藏 0 评论 0

plokmju88 发布了文章 · 2019-11-07

Kotlin 重载个方法,还有两幅面孔,省代码的同时也带来一个深坑 | Kotlin 原理

一. 序

今年五月的 Google I/O 上,Google 正式向全球宣布 Kotlin-First 这一重要概念,Kotlin 将成为 Android 开发者的首选语言。

新语言自然有新特性,还保持 Java 的编程习惯去写 Kotlin,也不是不行,但是总感觉差点意思。

最近公众号「谷歌开发者」连载了一个《实用 Kotlin 构建 Android 应用 | Kotlin 迁移指南》的系列文章,就举例了一些 Kotlin 编码的小技巧。既然是一种指南性质的文章,自然在「多而广」的基础上,有意去省略一些细节,同时举例的场景,可能还有一些不恰当的地方。

这里我就来补齐这些细节,今天聊聊利用 Kotlin 的方法默认参数的特性,完成类似 Java 的方法重载的效果。完全解析这个特性的使用方式和原理,以及在使用过程中的一个深坑。

二. Kotlin 的简易方法重载

2.1 Kotlin 如何简化方法重载?

在 Java 中,我们可以在同一个类中,定义多个同名的方法,只需要保证每个方法具有不同的参数类型或参数个数,这就是 Java 的方法重载

class Hello {
    public static void hello() {
        System.out.println("Hello, world!");
    }

    public static void hello(String name) {
        System.out.println("Hello, "+ name +"!");
    }

    public static void hello(String name, int age) {
        if (age > 0) {
            System.out.println("Hello, "+ name + "(" +age +")!");
        } else {
            System.out.println("Hello, "+ name +"!");
        }
    }
}

在这个例子中,我们定义了三个同名的 hello() 方法,分别有不同的逻辑细节。

在 Kotlin 中,因为它支持在同一个方法里,通过 「?」标出可空参数,以及通过「=」给出参数的默认值。那这三个方法就可以在 Kotlin 中,被柔和成一个方法。

object HelloDemo{
    fun hello(name: String = "world", age: Int = 0) {
        if (age > 0) {
            System.out.println("Hello, ${name}(${age})!");
        } else {
            System.out.println("Hello, ${name}!");
        }
    }
}

在 Kotlin 类中调用,和前面 Java 实现的效果是一致的。

HelloDemo.hello()
HelloDemo.hello("承香墨影")
HelloDemo.hello("承香墨影", 16)

但是这个通过 Kotlin 方法参数默认值的特性申明的方法,在 Java 类中使用时,就有些区别了。因为 HelloDemo 类被声明为 object,所以在 Java 中需要使用 INSTANCE 来调用它的方法。

HelloDemo.INSTANCE.hello("承香墨影",16);

Kotlin 中调用 hello() 方法很方便,可以选择性的忽略参数,但是在 Java 中使用,必须全量的显式的去做参数赋值。

这就是使用了参数默认值的方法申明时,分别在 Kotlin 和 Java 中的使用方式,接下来我们看看原理。

2.2 Kotlin 方法参数指定默认值的原理

Kotlin 编写的代码,之所以可以在 Java 系的虚拟机中运行,主要是因为它在编译的过程中,会被编译成虚拟机可识别的 Java 字节码。所以我们通过两次转换的方式(Show Kotlin Bytecode + Decompile),就可以得到 Kotlin 生成的对应 Java 代码了。

public final void hello(@NotNull String name, int age) {
  Intrinsics.checkParameterIsNotNull(name, "name");
  if (age > 0) {
     System.out.println("Hello, " + name + '(' + age + ")!");
  } else {
     System.out.println("Hello, " + name + '!');
  }
}

// $FF: synthetic method
public static void hello$default(HelloDemo var0, String var1, int var2, int var3, Object var4) {
  if ((var3 & 1) != 0) {
     var1 = "world";
  }

  if ((var3 & 2) != 0) {
     var2 = 0;
  }
  var0.hello(var1, var2);
}

在这里会生成一个 hello() 方法,同时还会有一个合成方法(synthetic method)hello$default,用来处理默认参数的问题。在 Kotlin 中调用 hello() 方法,会在编译期间,有选择性的自动替换成 hello() 的合成方法去调用。

// Kotlin 调用
HelloDemo.hello()
HelloDemo.hello("承香墨影")
HelloDemo.hello("承香墨影", 16)

// 编译后的 Java 代码
HelloDemo.hello$default(HelloDemo.INSTANCE, (String)null, 0, 3, (Object)null);
HelloDemo.hello$default(HelloDemo.INSTANCE, "承香墨影", 0, 2, (Object)null);
HelloDemo.INSTANCE.hello("承香墨影", 16);

注意看示例的末尾,当使用 hello(name,age) 这个方法重载时,其实与 Java 中的调用,是一致的,这没什么好说的。

这就是 Kotlin 方法重载时,使用指定默认参数的方式,省去多个方法重载代码的原理。

理解原理后,发现它确实减少了我们编写的代码量,但是有没有场景,是我们就需要显式的存在这几个方法的重载的?自然是有的,例如自定义 View 时。

三. 自定义 View 遇上 Kotlin

3.1 构造方法也是方法

再回到前面提到的谷歌开发者的《实用 Kotlin 构建 Android 应用 | Kotlin 迁移指南》系列文章中,举的例子其实很不恰当。

它这里的例子中,使用了 View 这个词,并且重载的几个方法,都是 View 的构造方法,我们在自定义 View 时,经常会和这三个方法打交道。

但是谷歌工程师在这里举的例子,很容易让人误会,实际上你如果在自定义 View 时,这么写一定是会报错的。

例如我们自定义一个 DemoView,它继承自 EditView。

class DemoView(
        context: Context, 
        attrs: AttributeSet? = null, 
        defStyleAttr: Int = 0
) : EditText(context, attrs, defStyleAttr) {
}

这个自定义的 DemoView,当使用在 XML 布局中时,虽然编译不会出错,但是运行时,你会得到一个 NoSuchMethodException。

Caused by: java.lang.NoSuchMethodException: <init> [class android.content.Context, interface android.util.AttributeSet]

什么问题呢?

在 LayoutInflater 创建控件时,找不到 DemoView(Context, AttributeSet) 这个重载方法,所以就报错了。

这其实很好理解,在前面说到 Kotlin 在使用带默认值的方法的原理,其实 Kotlin 最终会在编译后,额外生成一个合成方法,来处理方法的参数默认值的情况,它和 Java 的方法重载还不一样,用它生成的方法,确实不会存在多个方法的重载。

所以要明白,Kotlin 的方法指定默认参数与 Java 的方法重载,并不等价。只能说它们在某些场景下,特性是类似的。

3.2 使用 @JvmOverloads

那么回到这里的问题,在自定义 View 或者其他需要保留 Java 方法重载的场景下,怎么让 Kotlin 在编译时,真实的去生成对应的重载方法?

这里就需要用到 @JvmOverloads 了。

当 Kotlin 使用了默认值的方法,被增加了 @JvmOverloads 注解后,它的含义就是在编译时,保持并暴露出该方法的多个重载方法

其实当我们自定义 View 时,AS 已经给了我们充分的提示,它会自动帮我们生成带 @JvmOverloads 构造方法。

AS 帮我们补全的代码如下:

class DemoView @JvmOverloads constructor(
        context: Context, 
        attrs: AttributeSet? = null, 
        defStyleAttr: Int = 0
) : AppCompatEditText(context, attrs, defStyleAttr) {
}

再用「Kotlin Bytecode + Decompile」查看一下编译后的代码,来验证 @JvmOverloads 的效果。

@JvmOverloads
public DemoView(@NotNull Context context, @Nullable AttributeSet attrs, int defStyleAttr) {
  Intrinsics.checkParameterIsNotNull(context, "context");
  super(context, attrs, defStyleAttr);
}

// $FF: synthetic method
public DemoView(Context var1, AttributeSet var2, int var3, int var4, DefaultConstructorMarker var5) {
  if ((var4 & 2) != 0) {
     var2 = (AttributeSet)null;
  }

  if ((var4 & 4) != 0) {
     var3 = 0;
  }

  this(var1, var2, var3);
}

@JvmOverloads
public DemoView(@NotNull Context context, @Nullable AttributeSet attrs) {
  this(context, attrs, 0, 4, (DefaultConstructorMarker)null);
}

@JvmOverloads
public DemoView(@NotNull Context context) {
  this(context, (AttributeSet)null, 0, 6, (DefaultConstructorMarker)null);
}

可以看到,@JvmOverloads 生效后,会按照我们的预期生成对应的重载方法,同时保留合成方法,完成在 Kotlin 中使用时,使用默认参数的需求。

是不是以为到这里就完了?并不是,如果你在自定义 View 时,完全按照 AS 给你的提示生成代码,虽然程序不会崩溃了,但你会得到一些未知的错误。

3.3 View 中别直接用 AS 生成代码

在自定义 View 时,依赖 AS 的提示生成代码,会遇到一些未知的错误。例如在本文的例子中,我们想要实现一个 EditView 的子类,用 AS 提示生成了代码。

会出现什么问题呢?

在 EditView 的场景下,你会发现焦点没有了,点击之后软键盘也不会自动弹出。

那为什么会出现这种问题?

原因就在 AS 在自动生成的代码时,对参数默认值的处理。

当在自定义 View 时,通过 AS 生成重载方法时,它对参数默认值的处理规则是这样的。

  1. 遇到对象,默认值为 null。
  2. 遇到基础数据类型,默认值为基本数据类型的默认值。例如 Int 就是 0,Boolean 就是 false。

而在这里的场景下, defStyleAttr 这个参数的类型为 Int,所以默认值会被赋值为 0,但是它并不是我们需要的。

在 Android 中,当 View 通过 XML 文件来布局使用时,会调用两个参数的构造方法 (Context context, AttributeSet attrs),而它内部会调用三个参数的构造方法,并传递一个默认的 defStyleAttr,注意它并不是 0。

既然找到了问题,就很好解决了。我们看看自定义 View 的父类中,两个参数的构造方法如何实现的,将 defStyleArrt 当默认值传递进去就好了。

那我们先看看 AppCompatEditText 中的实现。

public AppCompatEditText(Context context, 
                         AttributeSet attrs) {
    this(context, attrs, R.attr.editTextStyle);
}

再修改 DemoView 中对 defStyleAttr 默认值的指定即可。

class DemoView @JvmOverloads constructor(
        context: Context,
        attrs: AttributeSet? = null, 
        defStyleAttr: Int = R.attr.editTextStyle
) : AppCompatEditText(context, attrs, defStyleAttr) {
}

到这里,自定义 View 中,使用默认参数的构造方法重载问题,也解决了。

在自定义 View 的场景下,当然也可以通过重写多个 constructor 方法来实现类似的效果,但是既然已经明白了它的原理,那就放心大胆的使用吧。

四. 小结时刻

到这里就弄清楚 Kotlin 中,使用默认参数来减少方法重载代码的使用技巧和原理,以及注意事项了。

弄清楚原理以及需要注意的点,可以帮助我们更好的使用 Kotlin 的特性。我们最后再总结一下本文的知识点:

  1. Kotlin 可以通过对一个方法的参数,通过指定默认值的方式,来完成类似 Java 中「方法重载」的效果。
  2. 若想保留 Java 的重载方法,可以使用 @JvmOverloads 注解标记,它会自动生成该方法的全部重载方法。
  3. 在自定义 View 时,需要注意指定参数 defStyleAttr 的默认值,而不应该是 0。

今天就到这里,对本文的内容你有什么问题嘛?欢迎留言讨论。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 1 收藏 1 评论 0

plokmju88 发布了文章 · 2019-11-05

常见的链表翻转,字节跳动加了个条件,面试者高呼「我太难了」| 图解算法

本文首发自公众号「承香墨影(ID:cxmyDev)」,欢迎关注。

一. 序

我又来讲链表题了,这道题据说是来自字节跳动的面试题。

为什么说是「据说」呢?因为我也是看来的,觉得题目还是挺有意思,但是原作者给出的方案,我想了想觉得还有优化空间,就单独拿出来讲讲。

就像本文的题目说的,这是一道关于链表翻转的题。链表的翻转,之前的文章也讲了很多,例如:链表翻转链表两两翻转K 个一组翻转链表。这些其实都是 leetcode 上的标准题,但是通常企业给出的面试题,多半会做一些变种,也就是加一些特殊的条件。

例如今天要讲的这道题。

给定单链表的头结点 head,实现一个调整链表的函数,从链表尾部开始,以 K 个结点为一组进行逆序翻转,头部剩余结点不足一组时,不需要翻转。(不能使用队列或者栈作为辅助)

仔细读题,像不像我们之前讲到的 leetcode 第 25 题K 个一组翻转链表

leetcode-25 是从头结点开始,以 K 个结点一组进行翻转。而字节跳动这道题,是从尾结点开始。

只是多了一个从尾结点开始分组翻转的条件,这道题的难度就增加了。

二. K个一组翻转链表(头条版)

2.1 其他人的解题思路

前面也说到,这道题是我看来的,当时是以一篇文章的形式发布出来。

文章我就不发了,不过先了解一下他的解题思路,有助于我们思考。

他的思路很清晰,虽然这道题他不会解,但是 leetcode-25 这个标准的以 K 个一组翻转链表的题他很熟悉。

那么可以先将原始链表,进行一次「链表翻转」,再进行「K 个一组翻转链表」,最后再做一次「链表翻转」还原链表,就得出了需要的结果。

ListNode revserseKGroupPlus(ListNode head, int k) {
  // 翻转链表
  head = reverseList(head);
  // K 个一组翻转链表
  head = reverseKGroup(head, k);
  // 翻转链表
  head = reverseList(head);
  return head;
}

把一个不熟悉的问题,经过简单的转换,变成熟悉的问题进行解决,这种思路是没有错的。

但是呢,有个问题--

在面试的场景中,通常来说,面试官的水平会高于面试者,那么我们可以简单的理解,面试就是一个不断受挫的过程,这个过程总会被问到我们知识的边界才会停止。

面试题只是起点,面试过程中深挖的哪些问题,才是触摸到我们谈薪资本的核心。当然这扯远了,继续回到本文的内容。

此时就算面试者当场写出了解题代码,也逃不开一个经典问题。

面试官:「还有更优的方案吗?

那么这道题,有没有更优的方案?答案当然是有的。

2.2 更优一点的方案

将链表先翻转后处理,再翻转回去,这样并不优雅,其实只需一次以 K 个一组翻转链表就可以。

再回忆一下 leetcode 第 25 题,它和这道题的差异,主要来自于,对不足一组的链表结点的处理。leetcode-25 是从头结点开始处理,所以多出来的结点会在尾部,而字节跳动这道题则正好相反,余下的结点会在头部。

但是它们同时也有一种特殊情况,就是 K 个一组进行分组时,这里的 K 正好可以完整的分组,一个不多,一个不少的分成 N 组。

当链表结点数量正好为 K * N 时,那么又回到了我们熟悉的 leetcode-25 题了。

如果我们先将原始结点进行处理,找出它正好可以整除 K 的起始结点 offset,将这个起始结点 offset 的子链表,再进行 K 个一组进行翻转链表,最后把它拼接回原始链表,就完成了这道题。

这个过程,需要额外定义两个结点,第一个满足 K 个分组条件的 offset 结点,以及 offset 的前驱结点 prev 结点,prev 结点主要是用来拼接翻转后的两个链表,让其不会出现链表断裂的问题。

它们的关系如下:

这其中还涉及到一些简单的链表运算,例如求链表的长度,这里就不展开说了,直接上核心代码,逻辑都在注释里,我们先定义一个 reverseKGroupPlus() 方法。

public ListNode reverseKGroupPlus(ListNode head, int k) {
    if (head == null || k <= 1) return head;
    // 计算原始链表长度
    int length = linkedLength(head);
      if (length < k) 
        return head;
  
    // 计算 offset
    int offsetIndex = length % k;

      // 原始链表正好可以由 K 分为 N 组,可直接处理
    if (offsetIndex == 0) {
        return reverseKGroup(head, k);
    }

    // 定义并找到 prev 和 offset
    ListNode prev = head, offset = head;
    while (offsetIndex > 0) {
        prev = offset;
        offset = offset.next;
        offsetIndex--;
    }
    // 将 offset 结点为起始的子链表进行翻转,再拼接回主链表
    prev.next = reverseKGroup(offset, k);
    return head;
}

注意当链表长度正好可以用 K 分为 N 组时,我们直接处理,否者才需要后续复杂的逻辑。

代码的注释足够清晰了,在脑子里过一遍代码的执行流程应该能明白,为了帮助大家理解,我又画了个示意图。

假设以 head 为头结点的链表长度是 10,K 为 4 时,那么计算下来 offset Index 就是 2。

找到 prev 和 offset 结点后,就可以将以 offset 结点为头结点的子链表,进行 K 个一组翻转链表的操作了。

此时,head 结点为起始的链表,就是我们计算后的结果。

2.3 再补一些额外的代码

这道题,还涉及到很多其他的小算法,本身 leetcode-25 就已经被定级为「困难」,字节跳动在这道题的基础上,又增加了难度。

为了保证解题的完整,这里再补充一些相关代码。

1.计算链表长度

private int linkedLength(ListNode head) {
    int count = 0;
    while (head != null) {
        count++;
        head = head.next;
    }
    return count;
}

没什么好说的,一个 while 循环搞定。

2.以 K 个一组翻转链表

这道题在之前的文章中详细讲解了,这里直接贴代码了。

public ListNode reverseKGroup(ListNode head, int k) {
    // 增加虚拟头结点
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // 定义 prev 和 end 结点
    ListNode prev = dummy;
    ListNode end = dummy;

    while(end.next != null) {
      // 以 k 个结点为条件,分组子链表
      for (int i = 0; i < k && end != null; i++)
        end = end.next;
      // 不足 K 个时不处理
      if (end == null)
        break;
      // 处理子链表
      ListNode start = prev.next;
      ListNode next = end.next;
      end.next = null;
      // 翻转子链表
      prev.next = reverseList(start);
      // 将子连表前后串起来
      start.next = next;
      prev = start;
      end = prev;
    }
    return dummy.next;
}

// 递归完成单链表翻转
private ListNode reverseList(ListNode head) {
    if (head == null || head.next == null)
      return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

对于 leetcode-25 这道题,还不太了解的可以看看之前的文章《K 个一组翻转链表》。

三. 小结时刻

以上就是我解这道题的思路,可能不是最高效的,但也算是比较清晰。

在面试过程中,链表相关的题目可以说是高频题。虽然企业在出题时,为了增加难度也会做一些变种,但是作为面试者,无论如何都避不开多练多写多想。

你有更好的方案吗?你在面试中有碰到什么奇葩的算法题吗?欢迎在留言区讨论。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料,也能回复『加群』,一起学习进步。

查看原文

赞 0 收藏 0 评论 0

plokmju88 发布了文章 · 2019-11-04

图解:K 个一组翻转链表 | LeetCode 级别:困难

本文首发自公众号:承香墨影(ID:cxmyDev),欢迎关注。

一. 序

链表作为一种基本的数据结构,本身理解起来很简单。它通过指针,将一组零散的内存空间(结点),串联起来,组成一个数据结构。

在面试的算法题中,经常会碰到链表相关的面试题。虽然链表的结构比较好理解,但是链表的题还是比较考教代码能力的。一些单链表的题,指针指来指去,很容易就把结点的 next 指针弄丢了,造成链表断裂。

链表翻转是一个面试中经常会碰到的题,在之前的文章中,也聊过单链表翻转链表双双翻转,今天再来聊聊它们的「升级版」,以 K 个为一组,翻转链表,同时这也是 LeetCode 的第 25 题。

二. K 个一组翻转链表

以 K 个结点为一组,将给定的单链表进行翻转。有点类似之前的链表两两翻转,只是那时的 K = 2。而在这道题中,K 变成一个外部传入的正整数,它是一个可变的值,并且小于或者等于链表的长度。

这道算法题,会用到之前的知识,既然 K 是可变的,我们无法估计 K 的大小,但是我们可以将原始链表,以 K 个结点为一组,执行单链表翻转的逻辑。

这就要用到之前《单链表翻转》的技巧了,不了解的建议先读读之前的文章。

既然需要将原始链表先以 K 个结点分组,再依次执行单链表翻转,在每组字链表翻转之后,还需要将它们再串起来,否者链表不就断裂了么。

这就需要使用两个变量 prev 和 end,分别记录子链表的前驱结点,以及子链表的尾结点。有了 end 这个子链表的尾结点,就可以很容易通过 end.next 拿到下一个子链表的头结点。

依据这几个结点,就可以完成子链表的翻转,以及保证在子链表翻转后依然可以串起来。

另外有一个特殊处理的地方,当原始链表以 K 个结点为一组分组时,末尾不满一组的子链表,保持原样不进行翻转。

参考链表两两翻转的思路,为了保证我们的代码逻辑统一,我们增加一个虚拟的头结点 dummy,来方便我们编写代码。

直接上代码,细节都在注释里。

class Solution {
  public ListNode reverseKGroup(ListNode head, int k) {
    // 增加虚拟头结点
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // 定义 prev 和 end 结点
    ListNode prev = dummy;
    ListNode end = dummy;
    
    while(end.next != null) {
      // 以 k 个结点为条件,分组子链表
      for (int i = 0; i < k && end != null; i++)
        end = end.next;
      // 不足 K 个时不处理
      if (end == null)
        break;
      // 处理子链表
      ListNode start = prev.next;
      ListNode next = end.next;
      end.next = null;
      // 翻转子链表
      prev.next = reverseList(start);
      // 将子连表前后串起来
      start.next = next;
      prev = start;
      end = prev;
    }
    return dummy.next;
  }
  
  // 递归完成单链表翻转
  private ListNode reverseList(ListNode head) {
       if (head == null || head.next == null)
      return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
  }
}

这里单链表的翻转,使用了递归,一般 K 值都不会太大,所以用递归没问题,当然你也可以换成循环实现。对细节不了解的,可以参见《单链表翻转》。

三. 小结时刻

到这里单链表,按 K 分组翻转的具体思路和代码,就介绍清楚了。我这种处理方式可能不是最高效的,但是应该是比较清晰的。

另外在实际面试中,其实很多场景下,都不会直接出 leetcode 上的算法题,都会稍微变种一下,但是大家要学会将复杂问题,转化为简单问题来解决。

到这里,链表翻转的基础题,基本上就说清楚了,包含三个篇文章:

今天就到这里,有任何问题欢迎留言讨论。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 0 收藏 0 评论 0

plokmju88 发布了文章 · 2019-10-30

面试官:"准备用HashMap存1w条数据,构造时传10000还会触发扩容吗?"

// 预计存入 1w 条数据,初始化赋值 10000,避免 resize。
HashMap<String,String> map = new HashMap<>(10000)
// for (int i = 0; i < 10000; i++)

Java 集合的扩容

HashMap 算是我们最常用的集合之一,虽然对于 Android 开发者,Google 官方推荐了更省内存的 SparseArray 和 ArrayMap,但是 HashMap 依然是最常用的。

我们通过 HashMap 来存储 Key-Value 这种键值对形式的数据,其内部通过哈希表,让存取效率最好时可以达到 O(1),而又因为可能存在的 Hash 冲突,引入了链表和红黑树的结构,让效率最差也差不过 O(logn)。

整体来说,HashMap 作为一款工业级的哈希表结构,效率还是有保障的。

编程语言提供的集合类,虽然底层还是基于数组、链表这种最基本的数据结构,但是和我们直接使用数组不同,集合在容量不足时,会触发动态扩容来保证有足够的空间存储数据

动态扩容,涉及到数据的拷贝,是一种「较重」的操作。那如果能够提前确定集合将要存储的数据量范围,就可以通过构造方法,指定集合的初始容量,来保证接下来的操作中,不至于触发动态扩容。

这就引入了本文开篇的问题,如果使用 HashMap,当初始化是构造函数指定 1w 时,后续我们立即存入 1w 条数据,是否符合与其不会触发扩容呢?

在分析这个问题前,那我们先来看看,HashMap 初始化时,指定初始容量值都做了什么?

PS:本文所涉及代码,均以 JDK 1.8 中 HashMap 的源码举例。

HashMap 的初始化

在 HashMap 中,提供了一个指定初始容量的构造方法 HashMap(int initialCapacity),这个方法最终会调用到 HashMap 另一个构造方法,其中的参数 loadFactor 就是默认值 0.75f。

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

其中的成员变量 threshold 就是用来存储,触发 HashMap 扩容的阈值,也就是说,当 HashMap 存储的数据量达到 threshold 时,就会触发扩容。

从构造方法的逻辑可以看出,HashMap 并不是直接使用外部传递进来的 initialCapacity,而是经过了 tableSizeFor() 方法的处理,再赋值到 threshole 上。

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

tableSizeFor() 方法中,通过逐步位运算,就可以让返回值,保持在 2 的 N 次幂。以方便在扩容的时候,快速计算数据在扩容后的新表中的位置。

那么当我们从外部传递进来 1w 时,实际上经过 tableSizeFor() 方法处理之后,就会变成 2 的 14 次幂 16384,再算上负载因子 0.75f,实际在不触发扩容的前提下,可存储的数据容量是 12288(16384 * 0.75f)。

这种场景下,用来存放 1w 条数据,绰绰有余了,并不会触发我们猜想的扩容。

HashMap 的 table 初始化

当我们把初始容量,调整到 1000 时,情况又不一样了,具体情况具体分析。

再回到 HashMap 的构造方法,threshold 为扩容的阈值,在构造方法中由 tableSizeFor() 方法调整后直接赋值,所以在构造 HashMap 时,如果传递 1000,threshold 调整后的值确实是 1024,但 HashMap 并不直接使用它。

仔细想想就会知道,初始化时决定了 threshold 值,但其装载因子(loadFactor)并没有参与运算,那在后面具体逻辑的时候,HashMap 是如何处理的呢?

在 HashMap 中,所有的数据,都是通过成员变量 table 数组来存储的,在 JDK 1.7 和 1.8 中虽然 table 的类型有所不同,但是数组这种基本结构并没有变化。那么 table、threshold、loadFactor 三者之间的关系,就是:

table.size == threshold * loadFactor

那这个 table 是在什么时候初始化的呢?这就要说会到我们一直在回避的问题,HashMap 的扩容。

在 HashMap 中,动态扩容的逻辑在 resize() 方法中。这个方法不仅仅承担了 table 的扩容,它还承担了 table 的初始化。

当我们首次调用 HashMap 的 put() 方法存数据时,如果发现 table 为 null,则会调用 resize() 去初始化 table,具体逻辑在 putVal() 方法中。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length; // 调用 resize()
    // ...
}

resize() 方法中,调整了最终 threshold 值,以及完成了 table 的初始化。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
    else if (oldThr > 0) 
        newCap = oldThr; // ①
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
          // ②
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // ③
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; // ④
      // ....
}

注意看代码中的注释标记。

因为 resize() 还糅合了动态扩容的逻辑,所以我将初始化 table 的逻辑用注释标记出来了。其中 xxxCap 和 xxxThr 分别对应了 table 的容量和动态扩容的阈值,所以存在旧和新两组数据。

当我们指定了初始容量,且 table 未被初始化时,oldThr 就不为 0,则会走到代码 的逻辑。在其中将 newCap 赋值为 oldThr,也就是新创建的 table 会是我们构造的 HashMap 时指定的容量值。

之后会进入代码 的逻辑,其中就通过装载因子(loadFactor)调整了新的阈值(newThr),当然这里也做了一些限制需要让 newThr 在一个合法的范围内。

在代码 中,将使用 loadFactor 调整后的阈值,重新保存到 threshold 中。并通过 newCap 创建新的数组,将其指定到 table 上,完成 table 的初始化(代码 )。

到这里也就清楚了,虽然我们在初始化时,传递进来的 initialCapacity 虽然被赋值给 threshold,但是它实际是 table 的尺寸,并且最终会通过 loadFactor 重新调整 threshold

那么回到之前的问题就有答案了,虽然 HashMap 初始容量指定为 1000,但是它只是表示 table 数组为 1000,扩容的重要依据扩容阈值会在 resize() 中调整为 768(1024 * 0.75)。

它是不足以承载 1000 条数据的,最终在存够 1k 条数据之前,还会触发一次动态扩容。

通常在初始化 HashMap 时,初始容量都是根据业务来的,而不会是一个固定值,为此我们需要有一个特殊处理的方式,就是将预期的初始容量,再除以 HashMap 的装载因子,默认时就是除以 0.75。

例如想要用 HashMap 存放 1k 条数据,应该设置 1000 / 0.75,实际传递进去的值是 1333,然后会被 tableSizeFor() 方法调整到 2048,足够存储数据而不会触发扩容。

当想用 HashMap 存放 1w 条数据时,依然设置 10000 / 0.75,实际传递进去的值是 13333,会被调整到 16384,和我们直接传递 10000 效果是一样的。

小结时刻

到这里,就了解清楚了 HashMap 的初始容量,应该如何科学的计算,本质上你传递进去的值可能并无法直接存储这么多数据,会有一个动态调整的过程。其中就需要将我们预期的值进行放大,比较科学的就是依据装载因子进行放大。

最后我们再总结一下:

  1. HashMap 构造方法传递的 initialCapacity,虽然在处理后被存入了 loadFactor 中,但它实际表示 table 的容量。
  2. 构造方法传递的 initialCapacity,最终会被 tableSizeFor() 方法动态调整为 2 的 N 次幂,以方便在扩容的时候,计算数据在 newTable 中的位置。
  3. 如果设置了 table 的初始容量,会在初始化 table 时,将扩容阈值 threshold 重新调整为 table.size * loadFactor。
  4. HashMap 是否扩容,由 threshold 决定,而 threshold 又由初始容量和 loadFactor 决定。
  5. 如果我们预先知道 HashMap 数据量范围,可以预设 HashMap 的容量值来提升效率,但是需要注意要考虑装载因子的影响,才能保证不会触发预期之外的动态扩容。

HashMap 作为 Java 最常用的集合之一,市面上优秀的文章很多,但是很少有人从初始容量的角度来分析其中的逻辑,而初始容量又是集合中比较实际的优化点。其实不少人也搞不清楚,在设置 HashMap 初始容量时,是否应该考虑装载因子,才有了此文。

如果本文对你有所帮助,留言、转发、点好看是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料,也能回复『加群』,一起学习进步。

查看原文

赞 1 收藏 1 评论 0

plokmju88 发布了文章 · 2019-10-18

图解算法:单链表两两反转 | 眼睛会了手就会系列

一. 序

链表作为一种基本的数据结构,本身理解起来,很简单。它通过指针或者叫引用,将一组零散的内存空间(结点),串联起来组成一个数据存储结构。

链表根据其指针的指向和丰富程度,可以分为单链表、双向链表、循环链表、双向循环链表。其差别就是,是否在单链表的基础上为结点,增加更丰富的指针,让其实现更丰富的功能。

链表虽然很好理解,但是链表的代码,写起来却并不是那么容易,尤其上一些对单链表的操作,例如链表反转、链表双双反转、有序链表合并等。

你可以自己试试,放下手机拿起纸笔,来一场模拟面试,就是写一个单链表两两反转,看看能否一次通过。

写链表代码的时候,指针指来指去,很容易就把指针丢失,造成链表断裂。所以在操作链表时,其操作顺序就是我们着重关注的点。

虽然链表代码写起来不容易,但链表又是面试的常客,一些常见的算法实现,也是我们开发者必须要掌握的。

之前写过单链表反转的三种解法(戳我了解),今天再来聊聊它的升级版,链表两两反转,这也是 Leetcode 第 24 题,算是面试常客了。

二. 单链表两两反转

2.1 什么是单链表两两反转?

单链表反转比较好理解,就是逆序嘛,但是两两反转是什么意思呢?

我们知道,单链表是由指针,将一个一个结点串联起来的数据结构。那么我们将这些结点,两个为一组,在组内进行反转,就是两两反转了。

单链表两两反转这种题,非常适合用递归的思想来解决,将每一步操作都封闭在一个小单元内,然后重复操作。

通常递归能做的,循环也能做,所以我们就这两种解法,分别讲解。

2.2 循环解法

无论是使用循环还是递归,其实都是将链表结点交换的步骤拆解,放在一个个小循环(递归)中去处理。相对于递归,循环法在结点的使用步骤上更清晰,我们就以循环法作为切入点。

递归或循环,其核心就是找到抽象模型,在每个调用步骤中,不断重复相同的事情。

在单链表两两反转中,看似是在处理两个结点,但其实是在处理 4 个结点之间的关系。

除了待反转的 A、B 两个结点之外,还需要操作 A 的前驱结点 prev 结点和 B 的 Next 结点 b-next 结点。

我们每次反转,其实就在操作这四个结点,其中的操作步骤很重要。

如图所示,步骤 ① 操作有两步操作,因为其操作的指针互不影响,所以在写代码的时候不分先后,在保证 prev 指针和 b-next 指针的指向无错后,就可以开始 A、B 结点的反转,也就是步骤 ②。

最后我们只需要将我们关注的结点前移,就可以进入下一次循环。

在这个步骤中,我们在操作 4 个结点的指针,但是其实每次初始的结点,只有 A 的前驱结点 prev 结点。为了保证循环内的操作一致,我们可以在链表前,加一个虚拟的头结点,来辅助我们,让代码更简洁。

到这里,各个步骤就清晰了,每次反转两个结点,然后前移 dummy 指针。

最后,还需要再注意一些边界条件,注意我们的循环,什么时候停止。

在单链表两两反转的场景下,链表的结点数,有单有双,当结点数为单数时,最后一个结点已经找不到可以反转交换的结点了,此时保持不变即可。

接下来直接上循环代码了,这里使用我们熟悉的 Java 代码来实现。

public ListNode swapPairs(ListNode head){
  // 链表头增加虚拟结点 dummy
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  head = dummy;
  // 循环退出条件,注意链表结点数单双的情况
  while(head.next != null && head.next.next != null){
    // 开始反转
    ListNode a = head.next;
    ListNode b = a.next;
    head.next = b; // 步骤①
    a.next = b.next; // 步骤①
    b.next = a; // 步骤②
    // dummy 指针前移
    head = a;
  }
  return dummy.next;
}

代码中的注释已经很清晰了,首先在链表头插入一个虚拟结点 dummy,之后开启循环,循环退出的条件就是走到了链表尾部的边界,需要注意结点数为单、双两种情况。之后再按照前文中图解的步骤,开始操作链表指针实现两两反转,最后前移 dummy 指针。

2.3 递归解法

递归的解法,相对于循环解法,代码量上就少很多,看着也清爽了。主要是因为递归,通过一层层的调用,在方法栈上存储了存储了一些变量就是我们待操作的结点。

在这里,在递归里,我们依然关注三个问题,递归解决的小问题、终止条件以及返回值。

递归的解法,直接看代码比较清晰。

public ListNode swapPairs(ListNode head) {
  if (head == null || head.next == null) {
    return head;
  }
  ListNode next = head.next;
  head.next = swapPairs(next.next);
  next.next = head;
  return next;
}

再结合之前操作步骤的图解。

递归的方法比较绕,结合上图,找到思路,循环是一次从前向后的移动操作窗口,而递推是从后向前移动操作窗口。注意递归终止条件以及每次递归操作时,结点指针的轮转,多想多练就清晰了。

三. 小结时刻

到这里对单链表的两两反转,就讲解完毕。

写链表代码,除了考验逻辑思维能力,还考验编码能力,多写多练才是核心。

注意其中的边界条件以及每个操作单元中,结点指针的交换轮转。这其中的每个步骤的操作顺序,都通过图解的方式讲解清楚了,有疑问欢迎在留言去讨论。

本文对你有帮助吗?留言、转发、收藏是最大的支持,谢谢!


公众号后台回复成长『成长』,将会得到我准备的学习资料。

查看原文

赞 0 收藏 0 评论 0

plokmju88 发布了文章 · 2019-09-23

Android 本地化适配:RTL(right-to-left) 适配清单

本文首发自公众号:承香墨影(ID:cxmyDev),欢迎关注。

一. 序

越来越多的公司 App,都开始淘金海外,寻找更多的机会。然而海外市场千差万别,无论是市场还是用户的使用习惯,都有诸多的不同。

当你接触一款出海 App 的时候,除了需要了解海外 Google Service 的整个生态圈,还要做好不同语言的适配。语言适配最通用的做法就是根据不同系统语言设定,配置不同的语言资源(strings.xml),而其中比较特殊的就是例如阿拉伯的 RTL 布局,它不仅改变了语言,还改变了 UI 布局和使用习惯。

我们常用的习惯,称之为 LTR(Left-To-Right),其意为我们的阅读和书写习惯,是从左向右延伸的。而 RTL(Right-To-Left) 则正好相反,它的阅读和使用的习惯都是从右向左,常见使用 RTL 习惯的语言有阿拉伯语、希伯来语等。

今天就来聊聊,一个成熟的 Android App,想要做 RTL 适配,需要关注什么,想要适配 RTL 有哪些任务清单。

如果你维护的 App 有国际化的要求,那这个问题是迟早需要面对的。

二. Android 支持 RTL

2.1 什么是 RTL?

正如前面介绍的,RTL 是 Right-to-left 的缩写,其意为阅读和书写的习惯,是从右向左延伸的。再对比一下我国人自身的使用习惯,都是 LTR 的,也就是从左向右。

RTL 可以简单理解是 LTR 的镜像,当需要适配 RTL 的时候,除了翻译语言本身,还需要做到的就是 UI 布局,从中轴上镜像反转。

虽然 RTL 不符合我们国人的使用习惯,但是全球范围内依然有一部分人保持着 RTL 的习惯,比较常见的就是阿拉伯语、希伯来语等。

就 Android 系统来说,Android 4.1 开始就在 TextView 和 EditView 中增加了对双向文本的优先支持,允许其文本内容从左向右(LTR)到从右向左(RTL)的显示和切换。而在 Android 4.2 开始,增加了对 RTL 镜像布局完全原生的支持。

也就是在 Android 4.2(Api Level 17)及之后,在 UI 上的布局镜像,是原生支持的。在这些系统版本上,只要用户系统语言切换到「RTL 系语言」,首先系统 UI 会直接左右镜像切换,此时如果你的 App 支持 RTL 镜像布局时,也会自动切换布局方向。

2.2 App 如何支持 RTL 镜像

正如前面介绍的一样,LTR 到 RTL 的切换,不是由开发者控制的,而通常是由系统语言来控制的。

当系统语言切换为「RTL 系语言」时,还需要你的 App 支持 RTL 镜像布局。

这里所谓的支持,其实只需要配置一个属性即可,就是 AndroidManifest.xml 配置文件中的一个清单元素。需要在 <applictaion> 标签下,配置元素 android:supportsRtl="true"

此时当系统语言切换的时候,你的 App 也会跟着切换 UI 布局为镜像后的效果。

除了需要开启 supportsRtl 属性之外,还需要一些布局属性的配合。

简单来说,就是将布局需要的所有 xxxLeft/xxxRight "替换"为 xxxStart/xxxEnd。

例如我们常用的 Padding 和 Margin,都有类似 paddingLeft 和 layout_marginRight 属性,这些就需要"替换"成 paddingStart 和 layout_marginEnd 属性。当然不止于此,还有一些 gravity、drawableLeft 等属性需要"替换"。原则上,所有 Left/Right 都需要变换为 Start/End 就好了。

这些属性,官方文档中已经帮我们列举出来了。

clipboard.png

到这里应该了解了,Android App 支持 RTL 镜像的主要流程,就两步:

  1. App 增加 android:supports="true" 属性。
  2. 调整 UI 布局属性,从 left/rightstart/end 切换。

那么问题来了,我们在日常编码的过程中,应该使用 left/right 还是 start/end?还是两者都需要?

注意到我前面提到的 UI 布局属性的替换时,是打了引号的,你是否需要使用 start/end 来完全替换 left/right ,完全取决于 App 当前的 minSdkVersion 值。

正如前面所提到的,Android 对 RTL 的原生支持,是在 Android 4.2 中才具备的,也就是说,如果 App 的 minSdkVersion 大于等于 4.2,你只需要使用 start/end 属性,但如果还需要支持 4.2 以下的设备用户,那就需要保留 left/rightstart/end 两者。

在低于 4.2 的系统中,不识别 supportsRtlstart/end 属性,所以不会造成影响。但是需要注意,在适配完成之后,后续开发新页面时的编码习惯。

2.3 AS 助力调整布局属性

如果当前需要适配的是一个成熟项目,并且其中的布局习惯还是使用 left/right 系的属性,那么针对所有页面布局文件,进行手工调整就是一个非常大的工作量了。

所幸的是 AS 提供了自动化的支持。

你可以在 Refactor → Add RTL Support Where Possible 来开启 RTL 的自动调整。

clipboard.png

它会自动将项目中所有的 left/right 属性都替换为 start/end 属性,如果想要适配 Android 4.2 以下的设备,需要保留两者,那么在 Run 之前,勾选 Relpace Left/Right Properties with Start/End Properties 选项即可。

早期的 AS 自动支持 RTL 布局的时候,效率会有一些问题,转换的时候如果布局过多,可能会卡死,但是新版的 AS 已经优化了很多,转换效率上还是可以接受的。

另外这毕竟是自动替换,在替换完成之后,还是需要每个页面都测试一遍,看看效果才算完,有时候还需要我们做一些微调的工作。例如 AS 自动替换 RTL 布局的时候,如果使用了 include 标签,其中用到的方向属性不会被替换。

自动化虽然方便了我们机械的重复,但也必须介入人工的干预符合预期。

三. RTL 细节调整

要做这种全全局的改动,必然会有一些细节需要微调的,这里简单写一些 RTL 布局中会需要使用到的细节调整技巧。

3.1 利用全局样式,批量修改属性

在适配 RTL 的过程中,无法避免的就是有一些属性必须要设置。例如 EditView 就需要设置以下属性。

android:textAlignment="viewStart"
android:gravity="start"
android:textDirection="locale"

那我们就可以将这些属性在 style.xml 中全局为 EditText 设置上。

<style name="AppTheme" parent="Theme.AppCompat.Light.NoActionBar">
       ...
       <item name="editTextStyle">@style/EditTextStyle.Alignment</item>
       ...
</style>

<style name="EditTextStyle.Alignment" parent="@android:style/Widget.EditText">
        <item name="android:textAlignment">viewStart</item>
        <item name="android:gravity">start</item>
        <item name="android:textDirection">locale</item>
</style>

同时 TextView 也需要设置 android:textDirection 属性,也可以采用相同的方法用 Style 的方式全局设置。

3.2 针对 RTL 的资源适配

除了布局上的适配之外,还有一些资源的适配,资源适配主要说两块内容:Drawable(mipmap) 以及 Layout 布局资源。

先来说说 Drawable 的适配。例如在不同方向的布局下,使用不同的图标。

clipboard.png

上图就是个很典型的例子,在调整布局到 RTL 时,还需要注意返回「」的图标也需要替换成「」。

这里依然使用 Android 对资源使用的限定符的方式,可以创建 drawable-ldrtl 目录,将翻转后的图标,放在这个目录下。如果需要限定 dpi,可以在目录名后面追加。

res/
  drawable/
    a.png  
  drawable-ldrtl/
    a.png  // 对标 drawable/a.png 的 RTL 图标
  drawable-xhdpi/
    b.png  
  drawable-ldrtl-xhdpi/
    b.png  // 对标 drawable-xhdpi/b.png 的 RTL 图标

接下来再说说 Layout 布局的 RTL 布局效果适配。有些特殊的页面,可能光镜像化还不够,还需要针对性的做一些 UI 上的调整,那最简单的做法就是做两套布局,互不影响。

既然 Drawable 可以通过资源限定符的方式,设置 RTL 布局下使用的图标,其实布局也可以。

对于布局文件,可以在目录下追加限定符 layout-ldrtl/,如果想对某个语言做布局适配,也可以增加语言限定,例如阿拉伯语可以用 layout-ar/

res/
  layout/
    main.xml  // 默认布局
  layout-ar/
    main.xml  // 阿拉伯语布局
  layout-ldrtl/
    main.xml  // RTL 布局

针对 RTL 的 UI 布局规范,Material Design 下有一个规范的文档(https://material.io/design/us...),设计师可以参考。

3.3 代码判断是否 RTL?

有些控件的属性,是通过代码动态调整的,那在使用的过程中,就需要在代码中,判断当前的环境,是 RTL 还是 LTF,才可以确定后续的属性设置。

通过获取 Configuration 的 locale 来判断当前的环境,为了兼容,在 TextUtilsCompat 下也提供了类似的方法。

public boolean isRtl() {
    return TextUtilsCompat.getLayoutDirectionFromLocale(
        getContext().getResources().getConfiguration().locale) ==         ViewCompat.LAYOUT_DIRECTION_RTL;
}

isRtl() 方法可以直接拿来使用,依此判断结果,执行后续的操作。

3.4 不是所有控件都支持 RTL

虽说从 Android 4.2 开始,原生支持 RTL 方向布局,但是也有一些控件是不支持的,例如 ViewPager,就不支持 RTL 的方向。

这其实没有什么很好的办法,要么和产品商量对此处的容忍,要么找一些其他的解决方案。

针对 ViewPager 的 RTL 化,在 Github 就有对应的开源库 RtlViewPager(https://github.com/diego-gome...) 可供使用。其原理也是将数据进行倒序重排,没什么好说的,源码不多,有兴趣可以自己看看。

四. 适配 RTL 要如何估期?

再来聊聊适配 RTL 时,估算开发周期的问题。

除了 App 本身在设计研发之初,就是为了中东的土豪设计的之外,多数情况下,我们都是因为各种外部原因,需要在一款成熟的 App 上,适配 RTL 镜像布局。例如市场验证有大量「RTL 系语言」的付费用户,或者产品经理认为存在「RTL 系语言」的潜在用户。

什么时候适配 RTL,完全是由外部因素决定的。但是当需要适配的时候,我们作为开发者,最直观要面对的现实问题就是,适配 RTL 需要做哪些事?这个任务需要多少时间能够完成?需要哪些人来配合,哪些任务是可以并行的?

要精确估计 App 的 RTL 化,很难,因为工作量主要来自适配,说到适配,工作量就可大可小了。App 大量使用第三方控件的就比只使用原生控件的工作量大;产品经理和设计师,允许部分页面适配有差异的,也会比高要求还原的工作量大。

这些在适配完成之前,谁也不知道效果如何,既然没有什么好的方法,那就试一试吧,只需要三步,你可以拿着一个明确的镜面翻转效果,来估计适配的难度。

  1. 设置 android:supportsRtl="true",让 App 支持 RTL。
  2. AS 自动转换布局属性,支持 RTL 布局效果。
  3. 打开开发者选项中的「强制使用从右到左的布局方向」,强制 RTL 布局。

此时你基本上可以看到一个 80% RTL 化的 App,剩下的就是把页面都检查一遍,看看有没有用到哪些控件不支持 RTL,哪些 Drawable 需要替换、哪些布局需要微调。然后针对性的调整即可。

有一些控件不支持 RTL 就会比较麻烦,有源码的就改改源码,没源码的就看有没有地方可以 Hook 解决。

总之需要做什么,清单是固定的。有了明确的任务,自然就容易估计开发周期了。

列举一下适配 RTL 的任务清单:

  1. App 支持 RTL,AS 自动转换布局属性支持 RTL,从开发者选项里强制 RTL 布局方向。
  2. 按页面排查,检查出需要翻转的 Drawable 资源,打包交给设计师,反转后替换。
  3. 检查布局翻转后的效果,和设计师确定需要适配翻转后的 UI 效果。
  4. 找到不支持 RTL 化的控件,可以从源码的角度分析,能改源码的改源码,不能改源码的尝试 Hook 解决或找替代方案。
  5. 翻译 RTL 系语言资源 strings.xml,放入对应的资源目录,例如阿拉伯语需要放入 /values-ar/strings.xml 目录,将系统语言切换到阿拉伯语,排查所有页面文字与控件的匹配度。
  6. 整体验收,微调效果。

其中需要和产品、设计、翻译配合的,都可以提前准备,让任务并行化。当然在适配的过程中,还有一些实际的问题,就需要遇到问题再解决问题了。

五. 小结时刻

本文聊了如何在一个成熟的 App 上,适配 RTL 镜像效果,以及如何快速的适配。最后还列出了一个适配时,需要调整关注的清单列表,希望对你有所帮助。

本文就到这里,如果有所帮助,留言、转发、点好看是最大的支持,谢谢!

reference:

https://material.io/design/us...

https://android-developers.go...

https://developer.android.com...


公众号后台回复成长『成长』,将会得到精心准备的学习资料。

clipboard.png

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 388 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2016-05-18
个人主页被 2.7k 人浏览