¿Cómo obtener el recuento en HashMap teniendo correspondencia?

Primero, cree una clase con dos campos, uno para representar el código de área (String) y otro para representar el número de teléfono (String). Una vez que esté completo, puede girar sin importar la cantidad de objetos necesarios; rellenarlo con los datos necesarios y luego almacenarlo en una Lista.

Una vez hecho esto, puede usar un groupingBy para contar el Número de números de teléfono que pertenecen a cada grupo (código de área) como este:

Map<String, Long> resultSet = 
       myList.stream()
             .collect(Collectors.groupingBy(ClassName::getAreaCode, Collectors.counting()));

O si solo quieres imprimir, entonces puedes hacer:

myList.stream()
      .collect(Collectors.groupingBy(ClassName::getAreaCode, Collectors.counting()))
      .forEach((k, v) -> System.out.println(String.join(":", k, v.toString())));

Suponiendo que tiene una clase Phone de la siguiente manera:

public class Phone {
    private final String areaCode;
    private final String number;

    public Phone(String areaCode, String number) {
        this.areaCode = areaCode;
        this.number = number;
    }

    public String getAreaCode() { return areaCode; }

    public String getNumber() { return number; }
}

Luego, una vez que tenga una lista de teléfonos, como este:

List<Phone> phoneNumbers = Arrays.asList(
    new Phone("351", "123456"),
    new Phone("351", "1234567"),
    new Phone("111", "678904"));

Puede usar transmisiones (como en respuesta de Aominè) o la método Map.merge, de esta manera:

Map<String, Integer> result = new HashMap<>();
phoneNumbers.forEach(phone -> result.merge(phone.getAreaCode(), 1, Integer::sum));

Esto itera la lista de números de teléfono y, para cada uno de ellos, coloca una entrada en el mapa result, siendo el código de área la clave y 1 el valor. Si, para el número de teléfono actual, el mapa ya contenía una entrada con su código de área, entonces, 1 se agrega al valor de esa entrada a través de la función de fusión Integer::sum.